VGCD - The Very Greatest Common Divisor

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

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: 

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

3
2
3
3
21
6765
610

1
3
5