피보나치 수의 최대공약수

피보나치 수열은 $F_0 = 0$, $F_1 = 1$이고 $n \ge 2$일 때 $F_n = F_{n-1} + F_{n-2}$로 정의한다. 앞부분을 늘어놓으면 0, 1, 1, 2, 3, 5, 8, 13, 21로 이어진다.

점화식을 풀면 일반항은 다음과 같다.

$F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right\}$

피보나치 수열은 성질이 많다. 예를 들어 다음 두 식이 성립한다.

$\sum_{i=1}^{n} F_i = F_{n+2} - 1, \qquad F_n \mid F_{kn} \quad (k = 0, 1, 2, \dots)$

이 문제에서는 두 피보나치 수의 최대공약수를 구한다. 두 정수 $N$, $M$이 주어지면 $\gcd(F_N, F_M)$을 계산한다. 값이 매우 크므로 $10^9 + 7$로 나눈 나머지를 출력한다. 나머지는 최대공약수를 구한 뒤에 취한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$)

다음 $T$개의 줄에 각각 두 정수 $N$, $M$이 공백 하나로 구분되어 주어진다. ($0 < N, M \le 10^9$)

각 테스트 케이스마다 $\gcd(F_N, F_M)$을 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다.