Doris has just learned about the Fibonacci sequence. Let $f[i]$ denote the $i$-th term of the sequence, where:

$$f[0] = 0$$ $$f[1] = 1$$ $$f[n] = f[n - 1] + f[n - 2], n \geq 2$$

Doris's supercomputer has generated an $n \times m$ table, where the number in the $i$-th row and $j$-th column is $f[\gcd(i, j)]$, and $\gcd(i, j)$ denotes the greatest common divisor of $i$ and $j$.

Doris has an $n \times m$ table and wants to know the product of all these numbers.

Since the product of these numbers is extremely large, Doris only wants to know the result modulo $1000000007$.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. Each of the following $T$ lines contains two integers $n$ and $m$.

Output

Output $T$ lines, where the $i$-th line is the result for the $i$-th test case.

Examples

Input 1

3
2 3
4 5
6 7

Output 1

1
6
960

Constraints

For $10\%$ of the data, $1 \leq n, m \leq 100$ For $30\%$ of the data, $1 \leq n, m \leq 1000$ Additionally, for $30\%$ of the data, $T \leq 3$ For $100\%$ of the data, $T \leq 1000, 1 \leq n, m \leq 10^6$