Greatest Common Divisor Problem

Given n pairs of positive integers (a_i, b_i), find the greatest common divisor (GCD) for each pair.

Input Format

• The first line contains an integer n.
• Each of the next n lines contains two integers a_i and b_i.

Output Format
Output n lines, each containing the GCD of the corresponding pair.

Data Range
1 ≤ n ≤ 10⁵
1 ≤ a_i, b_i ≤ 2 × 10⁹

Sample Input

2
3 6
4 6

Sample Output

3
2