题目描述

给定两个正整数 $a$ 和 $b$，求它们的最大公约数。

然而，$a$ 和 $b$ 都可能非常巨大。题目保证，每个输入整数都是某个如下形式的方阵的行列式：

$$\begin{pmatrix} 1 & 1 & 0 & \cdots & 0 \\ -1 & 1 & 1 & \ddots & \vdots \\ 0 & -1 & \ddots & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & 1 \\ 0 & \cdots & 0 & -1 & 1 \end{pmatrix}.$$

也就是说，该方阵主对角线上的元素均为 $1$，主对角线上方相邻位置的元素均为 $1$，主对角线下方相邻位置的元素均为 $-1$，其余元素均为 $0$。

请对每组数据输出 $\gcd(a,b)$。

输入格式

第一行包含一个整数 $T$，表示测试用例数量，满足

$$0<T<250.$$

每个测试用例包含两行：

• 第一行包含整数 $a$；
• 第二行包含整数 $b$。

保证：

$$0<a<10^{12540},\qquad 0<b<10^{12540}.$$

并且 $a,b$ 均为题目所述某个方阵的行列式。

输出格式

对于每个测试用例，输出一行一个整数，表示 $a$ 与 $b$ 的最大公约数。

样例输入

3
2
3
3
21
6765
610

样例输出

1
3
5