Given two integers a and b find their greatest common divisor.

Input

The first line of the input file contains number 0 < n < 1000 the amount of tests. The description of n test cases follow. The description of a test case consists of two lines. The first line contains integer a (0 < a < 10^12540), the second – integer b (0 < b < 10^12540). It is also known that all the numbers in the input file are the determinants of the square matrix of the form:

Output

For each test case print the greatest common divisor of integers a and b on a separate line.

Example

Input:
3
2
3
3
21
6765
610

Output:
1
3
5