说明

求两个自然数a,b的最大公约数。

输入格式

输入N+1行数据，第一行为一个数N，接下来的N行，每行输入两个数据a,b。

输出格式

输出N行，每行为对应输出的最大公约数。

样例

2
6 9
12 16

3
4