시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 52 19 17 36.957%

문제

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: 

\[\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 < 1012540), the second – integer b (0 < b < 1012540). 

출력

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

힌트