题目描述

最大公约数相信大家都会计算，但怎么借助 C++快速地计算呢?下面这个式子是辗转相除法的数学表达：

f(x,y)={ f(y,x%y)，y>0；x，y=0 }

输入格式

第一行输入一个整数 t（t≤100）。

然后会有 t 行，每行有两个整数 x（1≤x≤10⁹），y（1≤y≤10⁹）。

输出格式

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

输入样例 #1

1
6 8

输出样例 #1

2

输入样例 #2

1
36 135

输出样例 #2

9

输入样例 #3

1
216 405

输出样例 #3

27

数据范围

f(x,y)={ f(y,x%y)，y>0；

第一行输入一个整数 t（t≤100）。

然后会有 t 行，每行有两个整数 x（1≤x≤10⁹），y（1≤y≤10⁹）。