가장 위대한 최대공약수

시간 제한2초메모리 제한128 MB

요약

대각선이 1, 위 대각선이 1, 아래 대각선이 -1인 삼중대각 행렬의 행렬식 두 개가 주어질 때, 그 둘의 최대공약수를 구한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

두 정수 $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$ 의 최대공약수를 한 줄에 하나씩 출력한다.

예제1

예제 1
입력
```
3
2
3
3
21
6765
610
```
예상 출력
```
1
3
5
```