가장 위대한 최대공약수

문제

두 정수 $a$ 와 $b$ 의 최대공약수를 구하라. 각 수 $a$ 와 $b$ 는 다음과 같은 정사각 행렬의 행렬식(determinant)이다. 이 행렬은 주대각선의 원소가 모두 $1$ , 바로 위 대각선의 원소가 모두 $1$ , 바로 아래 대각선의 원소가 모두 $-1$ 이고 나머지 원소는 모두 $0$ 인 삼중대각(tridiagonal) 행렬이다.

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

입력

첫째 줄에 테스트 케이스의 개수 $n$ ( $n < 250$ )이 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 정수 $a$ ( $0 < a < 1012540$ )가, 둘째 줄에는 정수 $b$ ( $0 < b < 1012540$ )가 주어진다.

출력

각 테스트 케이스마다 $a$ 와 $b$ 의 최대공약수를 한 줄에 하나씩 출력한다.