Given two positive integers, find their greatest common divisor.

First line of input will contain an integer T = number of test cases . Next T lines will each contain two numbers A and B separated by space. 1<= A,B <= 10^15

For each test case, print on a single line the greatest common divisor of the two numbers.

5 2 4 11 17 35 14 55 15 12345 123

2 1 7 5 3

1) See input limit for A and B. 32 bit integer will overflow. 2) You need to think of an O(log n) algorithm. 3) Have you heard of a mathematician named Euclid?