最大公约数相信大家都会计算，但怎么借助 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 的最大公约数。