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.
Case 1: t<=100, a, b<=100
Case 2: t<=10000, a, b<=10000
Case 3: t<=20000, a, b<=100000
Case 4: t<=25000, a, b<=1000000
For each case, output the GCD of a and b in a line.