GCD of Fibonacci Numbers

The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$. It starts 0, 1, 1, 2, 3, 5, 8, 13, 21.

Solving the recurrence gives a closed form.

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

The sequence has many properties. Two of them are the following.

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

This problem asks for the greatest common divisor of two Fibonacci numbers. Given two integers $N$ and $M$, compute $\gcd(F_N, F_M)$. The value is huge, so print it modulo $10^9 + 7$. Take the remainder after computing the greatest common divisor.

The first line contains the number of test cases $T$. ($1 \le T \le 1000$)

Each of the next $T$ lines contains two integers $N$ and $M$ separated by one space. ($0 < N, M \le 10^9$)

For each test case, print $\gcd(F_N, F_M)$ modulo $10^9 + 7$ on its own line.