题目描述

给定两个正整数 $a$ 和 $b$，求他们的最大公因数（最大公约数）$gcd(a,b)$。

公因数（公约数）：如果一个整数同时是几个整数的因数，称这个整数为它们的“公因数”

输入格式

第一行一个整数 $T$，表示共有 $T$ 组数据。

接下来的 $T$ 行，每行两个整数 $a$ 和 $b$

输出格式

共 $T$ 行，每行对应一组数据的答案

样例数据

4
2 4
18 27
7 9
121 33

2
9
1
11

数据范围

对于$100\%$的数据，$1 \le T \le 10^5, 1 \le a,b \le 10^{16}$。