编程题：3001 最大公约数

输入两个整数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







答案：若无答案欢迎评论