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

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

输入格式

第一行输入一个整数t(t≤100)。

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

输出格式

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

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

样例输入

1
6 8

样例输出

2