题目描述

围棋有本手，妙手，俗手，但是数学还有苦手。而盖亚就是数学苦手。他的数学非常差，甚至无法计算3与6的最大公约数。$a$ 与 $b$ 的最大公约数是能够同时被 $a$ 与 $b$ 整除的最大正整数。 现在盖亚的数学老师给了他 $n$ 对数字，希望他计算 $n$ 对数字的最大公约数， 你可以帮帮他吗。

输入格式

第一行输入一个整数 $n(1 \leq n \leq 100000)$，表示有 $n$ 对数字需要计算最大公约数。 从第 $2$ 行到第 $n + 1$ 行，每行输入两个正整数 $x_i, y_i(1\leq x_i, y_i, \leq 10^9)$。

输出格式

输出 $n$ 行，每行一个正整数，第 $i$ 行输出 $x_i, y_i$ 的最大公约数。

3

1 4

2 4

9 6

1

2

3