The question is simple and straight forward in language.

You have to find the GCD of two numbers A and B .

Input

The first line of the input file contains a number T representing the number of lines to follow. Each line consists of two number A and B

Output

For each T lines print the gcd of A and B.

Constraints

1 <= T <= 10 ^ 4

0 <= A <= 40000 and A <= B < 10^250