题目背景

我们规定，对于两个正整数 $a,b$：

• 最大公因数（Greatest Common Divisior，GCD）：最大的正整数 $x$，满足 $a \div x$，$b \div x$ 的余数均为 $0$；
• 最小公倍数（Least Common Multiple，LCM）：最小的正整数 $x$，满足 $x \div a$，$x \div b$ 的余数均为 $0$。

例如对于 $a=12,b=30$，它们的最大公约数为 $6$，最小公倍数为 $60$。

题目描述

现在小 A 有两个大西瓜。第一个大西瓜的半径为 $a_1$，第二个大西瓜的半径为 $a_2$。

现在小 A 要合成大西瓜。具体而言，如果他手上的两个西瓜奇偶相同，则新的大西瓜的半径是小 A 手上两个西瓜的最大公约数，反之新的大西瓜的半径是小 A 手上两个西瓜的最小公倍数。

每次合成完大西瓜之后，小 A 手上最先有的西瓜会被丢弃。例如说，如果小 A 用第一个大西瓜和第二个大西瓜合成出第三个大西瓜，其半径为 $a_3$，则第一个大西瓜就被丢弃了；接着小 A 用第二个大西瓜和第三个大西瓜合成出第四个大西瓜，其半径为 $a_4$，则第二个大西瓜就被丢弃了。

小 A 想要知道，第 $k$ 个大西瓜的半径会是多少，请你告诉他。由于他要进行 $T$ 次合成大西瓜的游戏，因此你需要回答 $T$ 次问题。

输入格式

第一行输入一个正整数 $T$，表示询问次数。

第二行开始，一共 $T$ 行，每行表示一个询问：

• 每一行三个正整数 $a_1,a_2,k$，表示第一个大西瓜的半径、第二个大西瓜的半径，以及小 A 想要知道半径的大西瓜是第几个。

输出格式

对于每次询问，输出一行一个正整数，表示第 $k$ 个大西瓜的半径会是多少。

样例 #1

样例输入 #1

3
1 2 3
3 5 3
6 8 45

样例输出 #1

2
1
2

提示

【样例解释】

• 对于第一次询问，因为第一个和第二个大西瓜的半径奇偶性不同，因此第三个大西瓜的半径为第一个和第二个大西瓜半径的最小公倍数，即 $a_3=2$；
• 对于第二次询问，因为第一个和第二个大西瓜的半径奇偶性相同，因此第三个大西瓜的半径为第一个和第二个大西瓜半径的最大公约数，即 $a_3=1$；
• 对于第三次询问：
  • 因为第一个和第二个大西瓜的半径奇偶性相同，因此第三个大西瓜的半径为第一个和第二个大西瓜半径的最大公约数，即 $a_3=2$；
  • 因为第二个和第三个大西瓜的半径奇偶性相同，因此第四个大西瓜的半径为第二个和第三个大西瓜半径的最大公约数，即 $a_4=2$；
  • 以此类推，可得第 $45$ 个西瓜的半径为 $2$。

【数据范围】

对于 $30\%$ 的数据，$1 \leq T \leq 10$，$1 \leq a_1,a_2,k \leq 100$；

对于 $60\%$ 的数据，$1 \leq T \leq 100$，$1 \leq a_1,a_2,k \leq 10^4$；

对于所有数据，$1 \leq T \leq 10^5$，$1 \leq a_1,a_2 \leq 10^9$，$1 \leq k \leq 10^{18}$。