This practice problem will require you to programme basic functions.

Your task is to determine the greatest common divisor (GCD) of two integers.

This can be computed using the Euclidean algorithm, given input \(a > b\):

func gcd(a, b):
    if (b == 0) return a;
    q = a % b
    return gcd(b, q)

Here, % is the modulo operator which gives you the remainder of a division.

Input Specification

The first line will contain a single integer \(N\) (\(1 < N < 10000\)), indicating the number of test cases.

The following \(N\) lines will each contain a 2 integers \(a\) and \(b\) (\(1 < a,b < 100000000\)), for which you need to determine their GCD.

Output Specification

The output should contain \(N\) lines, each line an integer, which is the GCD for the \(i\)th input pair.

Sample Input

2
2 8
221 3400

Sample Output

2
17