题目描述

Doris 刚刚学习了 fibonacci 数列。用 $f_i$ 表示数列的第 $i$ 项，那么

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

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

答案对 $10^9+7$ 取模。

输入格式

本题单个测试点内有多组测试数据。

输入的第一行是一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行两个整数 $n, m$，表示一组数据。

输出格式

对于每组数据，输出一行一个整数表示答案。

3
2 3
4 5
6 7

1
6
960

提示

• 对于 $10\%$ 的数据，保证 $n,m\leq 10^2$。
• 对于 $30\%$ 的数据，保证 $n,m\leq 10^3$。
• 另有 $30\%$ 的数据，保证 $T\leq 3$。
• 对于 $100\%$ 的数据，保证 $1 \leq T\leq 10^3$，$1\leq n,m\leq 10^6$。