Find GCD (greatest common divisor) of two non-negative integers using Euclid’s algorithm.

Input

Input begins with t (1 ≤ t ≤ 100,000) of number of test-cases in the first line and the test-cases are in the following lines. Each test-case has m and n (1 ≤ m, n ≤ 1,000,000) on a single line separated by a space.

Output

For each test-case, print the GCD of m and n in a new line.

Example

Input:
5
60 24
100 101
120 420
0 123
123 0

Output:
12
1
60
123
123