题目背景

冒险家 fervor_w 在遗迹中发现刻有数字的神秘石板，旁边还刻着奇怪的符号 $gcd$ 。研究古籍后，他得知只有找出石板数字与 $gcd$ 代表数值的最大公约数，才能解开通往宝藏的密码。

fervor_w 日夜钻研，尝试用辗转相除法、分解质因数等方法计算。过程中，他遇到了许多难题，甚至一度陷入困境，但始终没有放弃。终于，在不断尝试与验证后，他成功算出了最大公约数，他简直是当代欧几里德！

当 fervor_w 将答案输入机关，古老的石门缓缓打开，里面藏着珍贵的文物和失传的知识。这次冒险让 fervor_w 深刻体会到，最大公约数不仅是破解密码的关键，更是探索未知世界的有力工具。

题目描述

给定 $a、b、c$ ，请你求出

$gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(b,a)},\frac{c}{gcd(b,c)})$

$gcd(a,b)$ 为 $a,b$ 的最大公约数，可以通过欧几里德算法求出

给出欧几里德算法的递归代码

int euclid(int a,int b)
{
  return b==0?a:euclid(b,a%b);
}

这段代码能够在 $log_{2}(max(a,b))$ 时间复杂度内求出两个数的最大公因数

多组测试用例

输入格式

第一行两个整数 $T$ ，代表测试样例数。$1\leq T \leq 10^{5}$。

接下来 $T$ 行 每行 $3$ 个整数 $a,b,c$。$1\leq a,b,c\leq 10^{50}$。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

输入输出样例 #1

输入 #1

1
2 2 2

输出 #1

1

说明/提示

提示

由于输入的数字过大，请考虑用别的数据类型输入