Description

给出两个正整数，求出它们的最大公约数。

Input Format

第一行输入一个整数n(0 <n≤1000)，表示有 n 组测试数据，随后的n行输入两个整数x,y，表示有 n 组测试数据

Output Format

根据题意输出

3
2 3
8 12
12 24

1
4
12

Source

信奥星OJ http://127.0.0.1