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?