Consider a series $$F$$ that is defined as follows:

F(1) = 1
F(2) = 1
F(3) = 2
For n >= 3, \(F(n)^2 - F(n + 1) \times F(n -1) = (-1)^n\)

Given two integers n and m. We need to make the \(n^{th}\) term and \(m^{th}\) term of the series co-prime. Find the largest positive number by which we must divide the \(n^{th}\) term and \(m^{th}\) term of the series such both terms become co-prime. Since, this number can be very large, print it modulo \(10^9 + 7\).

Note: Two numbers are said to be co-prime if there does not exist any number greater than 1, which divides both the numbers.

Input format

The first line contains an integer $$T$$ denoting the number of test cases.
For each test case:
- The first line contains a string denoting the integer $$n$$.
- The second line contains an integer $$m$$.

Output format

For each test case in a new line, find the required largest positive number modulo \(10^9 + 7\).

Constraints

\(1 \le T \le 100 \\ 1 \le n \le 10^{10^5} \\ 1 \le m \le 10^9\)