输入两个整数a，b(1<=a,b<=100000000)，请编写程序求出他们的最大公约数。

### 输入格式:

第一个数n表示测试数据的个数，接下来的n行每行有两个整数a和b，空格隔开。

### 输出格式:

输出n行，每行输出对应a，b的最大公约数。

### 输入样例:

in
3
12 8
25 10
21 63


### 输出样例:


out
4
5
21







答案：若无答案欢迎评论