Given two positive integers, find their greatest common divisor.
InputFirst 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
OutputFor each test case, print on a single line the greatest common divisor of the two numbers.
Sample Input5 2 4 11 17 35 14 55 15 12345 123Sample Output
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?