The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements $f_0$ and $f_1$ which are respectively zero and one. The first few numbers in the Recaman's Sequence is $0,1,1,2,3,5,8,...$. The $i$th Fibonacci number is denoted $f_i$.

The largest integer that divides both of two integers is called the greatest common divisor of these integers. The greatest common divisor of $a$ and $b$ is denoted by $gcd(a,b)$. Two positive integers $m$ and $n$ are given, you are expected to compute the $GCD(f_m ,f_n )$.

The first line contains one integer $T(T ≤ 100)$, the number of test cases.
For each test case,there are two positive integers $m$ and $n$ in one line. $(1 ≤ m,n ≤ 2^{31} , GCD(m,n) ≤ 45)$

For each the case, your program will output the $GCD(f_m ,f_n )$.