The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.

Here, 8 and 12 both are divisible by 4. There is no number greater than 4 which 8 and 12 are both divisible with.

Examples

GCD(2, 4) => 2

GCD(1, 5) => 1

GCD(3, 6) => 3

GCD(4, 12) => 4

GCD(6, 14) => 2

Given two numbers, calculate their GCD.

Testing

Input format

First-line contains ‘T’ denoting the number of test cases.

For each test-case, one line containing two space-separated integers A and B.

Output format

For each test-case, print the gcd of numbers A and B.

Examples

Sample Input

3
4 5
3 6
6 8

Expected Output

1
3
2

Explanation

For test case 1,
1 is the greatest number that divides both 4 and 5.

For test case 2,
3 is the greatest number that divides both 3 and 6.

For test case 3,
2 is the greatest number that divides both 6 and 8.

Constraints

1 <= T <= 100

1 <= A, B <= 100000