The Very Greatest Common Divisor

Time limit2sMemory limit128 MB

Summary

Each input value is the determinant of a tridiagonal n by n matrix with 1 on the diagonal, 1 above, -1 below; find the gcd of two such determinants.

Level: Medium7 of 10
Topics: Number theory, Math, Dynamic programming, Matrix
Solved: No attempts yet

Problem

Find the greatest common divisor of two integers $a$ and $b$ . Each of the numbers $a$ and $b$ is the determinant of a square matrix of the following form. It is a tridiagonal matrix whose main-diagonal entries are all $1$ , whose superdiagonal entries are all $1$ , whose subdiagonal entries are all $-1$ , and all of whose other entries are $0$ .

\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}

Input

The first line contains the number of test cases $n$ ( $n < 250$ ). Each test case consists of two lines: the first line contains an integer $a$ ( $0 < a < 1012540$ ) and the second line contains an integer $b$ ( $0 < b < 1012540$ ).

Output

For each test case, print the greatest common divisor of $a$ and $b$ on its own line.

Examples1

Example 1
Input
```
3
2
3
3
21
6765
610
```
Expected output
```
1
3
5
```