問題文

$N$ 個の以下の問題を解いてください。

• 整数 $A_i$ と整数 $B_i$ の最大公約数を求めよ。

制約

入力は以下の条件を満たす。

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i,B_i \\leq 10^9$
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$

出力

$i\\ (1 \\leq i \\leq N)$ 行目に $A_i$ と $B_i$ の最大公約数を出力せよ。

入力例 1

4
6 15
20 19
240 240
555555555 999999999

出力例 1

3
1
240
111111111