7487번 - The Very Greatest Common Divisor 다국어

문제

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 < 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.

제한

힌트