项链是人体的装饰品之一，是最早出现的首饰。项链除了具有装饰功能之外，有些项链还具有特殊显示作用，如天主教徒的十字架链和佛教徒的念珠。 从古至今人们为了美化人体本身，也美化环境，制造了各种不同风格，不同特点、不同式样的项链，满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论，首饰市场上的项链有黄金、白银、珠宝等几种。珍珠项链为珍珠制成的饰品，即将珍珠 钻孔后用线串在一起，佩戴于项间。天然珍珠项链具有一定的护养作用。

最近，铭铭迷恋上了一种项链。与其他珍珠项链基本上相同，不过这种项链的珠子却与众不同，是正三菱柱的泰山石雕刻而成的。三菱柱的侧面是正方形构成的，上面刻有数字。 能够让铭铭满意的项链必须满足下面的条件：

1. 这串项链由 $n$ 颗珠子构成的。
2. 每一个珠子上面的数字 $x$ ,必须满足 $0 < x \leq a$，且珠子上面的数字的最大公约数要恰好为 $1$。两个珠子被认为是相同的，当且仅当他们经过旋转，或者翻转后能够变成一样的。
3. 相邻的两个珠子必须不同。
4. 两串项链如果能够经过旋转变成一样的，那么这两串项链就是相同的！

铭铭很好奇如果给定 $n$ 和 $a$，能够找到多少不同串项链。由于答案可能很大，所以对输出的答案 $\bmod 1\,000\,000\,007$。

输入格式

数据由多组数据构成：

第一行给定一个 $T \leq 10$，代表有 $T$ 组数据。

接下来 $T$ 行，每行两个数 $n$ 和 $a$。

输出格式

对于每组数据输出有多少不同的串。

样例数据

样例输入

1
2 2

样例输出

3

子任务

对于 $20\%$ 的数据，$T = 1$。

另有 $10\%$ 的数据，$n \leq 10, a \leq 10$。

另有 $10\%$ 的数据，$n \leq 10^3, a \leq 100$。

另有 $20\%$ 的数据，$n \leq 10^6, a \leq 10^5$。

另有 $20\%$ 的数据，$n \leq 10^9, a \leq 100$。

另有 $10\%$ 的数据，$n \leq 10^9, a \leq 10^5$。

对于 $100\%$ 的数据：所有的 $1 \leq n \leq 10^{14}, 1 \leq a \leq 10^7, 1 \leq T \leq 10$。