题目描述

现在有$n$次查询，每次查询给定两个正整数$x,y$的最大公约数

输入格式

第一行一个整数$n$

接下来$n$行，每行两个正整数$x,y$

输出格式

按要求输出$n$行，每行为两个数的最大公约数

样例数据

input

1
15 25

output

5

数据规模与约定

保证 $n \le 100000,10\le x,y\le10^9$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$