题目描述

Doris 刚刚学习了 fibonacci 数列，用 $ f[i] $ 表示数列的第 $ i $ 项，那么：

$$ \begin{aligned} f[0] &= 0 \ f[1] &= 1 \ f[n] &= f[n - 1] + f[n - 2], n \geq 2 \end{aligned} $$

Doris 用老师的超级计算机生成了一个 $ n \times m $ 的表格，第 $ i $ 行第 $ j $ 列的格子中的数是 $ f[\gcd(i, j)] $，其中 $ \gcd(i, j) $ 表示 $ i $ 与 $ j $ 的最大公约数。

Doris 的表格中共有 $ n \times m $ 个数，她想知道这些数的乘积是多少。

这些数的乘积实在是太大了，所以 Doris 只想知道乘积对 $ 1000000007 $ 取模后的结果。

输入格式

有多组测试数据。
第一行一个数 $ T $，表示数据组数。
接下来 $ T $ 行，每行两个数 $ n $ 和 $ m $。

输出格式

输出 $ T $ 行，第 $ i $ 行的数是第 $ i $ 组数据的结果。

样例

input

3
2 3
4 5
6 7

output

1
6
960

数据范围与提示

对于 $ 10\% $ 的数据，$ 1 \leq n, m \leq 100 $；
对于 $ 30\% $ 的数据，$ 1 \leq n, m \leq 1000 $；
另外存在 $ 30\% $ 的数据，$ T \leq 3 $；
对于 $ 100\% $ 的数据，$ 1 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1000 $。