最大公约数相信大家都会计算，但怎么借助 C++ 快速地计算呢？

下面这个式子是辗转相除法的数学表达：

$\displaystyle f(x,y) = \begin{cases} f(y,x\%y) && y>0 \\ x && y=0 \end{cases}$​

输入格式

第一行输入一个整数$t(t \le 100)$)。

然后会有$t$ 行，每行有两个整数 $x(1 \le x \le 10^{9})$，$y(1 \le y \le 10^9)$。

输出格式

一共输出 $t$ 行，每行输出 $x,y$ 的最大公约数。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

1
6 8

样例输出

2