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.
First line contains a positive integer t (t<=1000), 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 106.
For each case, output the GCD of a and b in a line.
Note that you have to printf "\n" in the end.