解题思路

先看一次函数：

分两种情况：

题目内容

给定整数 $a,b,n$，定义 $f(x)=min(x,b)+gcd(x,b)$。记 $f^{(1)}(x)=f(x)$，$f^{(k+1)}(x)=f(f^{(k)}(x))$。请计算 $f^{(n)}(a)$ 的值。

【名词解释】 最大公约数$(gcd)$：指两个或多个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$，其中最大的约数是 $6$ ，因此记作 $gcd(12,30)=6$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤2×10^3)$ 代表数据组数，每组测试数据描述如下：

接下来 $T$ 行，每行输入三个整数 $a,b,n$，满足 $1≤a,b≤10^{12},1≤n≤10^{18}$。

输出描述

输出 $T$ 行，每行一个整数，表示对应数据的 $f^{(n)}(a)$ 的值。

样例1

输入

4
7 3 4
10 2 3
3 10 2
6 50 100

输出

4
4
6
100

说明

当 $(a,b,n)=(7,3,4)$：

$f(7)=min(7,3)+gcd(7,3)=3+1=4$，之后保持为 $4$ 。

当 $(a,b,n)=(3,10,2)$：

$f(3)=3+gcd(3,10)=4,$

$f(4)=4+gcd(4,10)=6$。