Description
Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.
Hint:
To compute gcd(48,18), divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd
Input
First line contains a positive integer t (t<=10000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10^6.
Output
For each case, output the GCD of a and b in a line.