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.