说明

嘤嘤嘤和喵喵喵都是18级的ACM萌新选修了天津工业大学的数论课程，在ACM的圈子流传着一句话：“数论只会GCD”，借以自嘲自己的数论水平低下，可见GCD，也就是最大公因数在数论里面是多么基础的一个算法啊！！！

现在老师给嘤嘤嘤和喵喵喵两个数$ X,Y$,让他们算出$ X,Y$的最大公因数，谁算的快就给谁的平时成绩加分，嘤嘤嘤知道自己肯定算不过喵喵喵，所以他求助于小乌嘎，于是小乌嘎把这个任务交给你这个优秀的代码手，希望你可以写一个程序，帮他算出最大公因数。（注:任何数和0最大公因数为该数本身）

输入格式

输入的第一行包含一个整数$T$，表示有$T$组数据$ T < 1000$接下来的T行，每行两个数$ X,Y$表示老师给出的两个数$(1 \leq X,Y \leq 2^{31} - 1)$

输出格式

输出包括T行，每行一个整数，表示$X,Y$的最大公因数

样例

2
10 5
6 4

5
2