You need to find greatest common divisor of two integers a and b. Each number a and b are determinants of the square matrix of the form: </p>

[\begin{pmatrix} 1 & 1 & 0  & \cdots & 0 \ -1 & 1 & 1 & \ddots  & \vdots \ 0 & -1 & \ddots & \ddots & 0 \ \vdots & \ddots & \ddots & \ddots & 1 \ 0 & \cdots & 0 & -1 & 1  \end{pmatrix}]

입력 형식

The first line of the input file contains number n < 250 of test cases. The description of a test case consists of two lines. The first line contains integer a (0 < a < 10¹²⁵⁴⁰), the second – integer b (0 < b < 10¹²⁵⁴⁰). 

출력 형식

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