成對數字的最大公因數

題目敘述

社團要把 a 本漫畫和 b 本小說分給若干組，每一組分到的漫畫數相同、小說數也相同，且所有書都要分完。最多能分成幾組？這個數正是 a 與 b 的最大公因數 gcd(a,b)。

共有 q 筆詢問，請對每一筆輸出 gcd(a,b)。

輸入格式

• 第一行：q
• 接下來 q 行，每行兩個整數 a、b

輸出格式

輸出 q 行，第 i 行是第 i 筆詢問的答案。

限制

• 1 ≤ q ≤ 2· 10⁵
• 1 ≤ a,b ≤ 10⁹

範例

範例 1

輸入

3
12 18
7 3
100 25

輸出

6
1
25

範例 2

輸入

1
1 1

輸出

1

說明

第一筆範例的三筆詢問中，12 與 18 的最大公因數是 6，7 與 3 互質所以是 1，100 與 25 則是 25。