You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

欧拉说他想你了于是有了这道题

Description

就不啰嗦了，这道题很简单，只需要求出 $F(x)= \frac{1}{p(x) \times k} \ mod \ 10^9+7$ 就好啦 , 其中的 $p(x)$ 表示的是小于 $x$ 且和 $x$ 互质的数的个数（注意这里我们定义1和任何数互质）， 例如对于数字 $6$ 来说和它互质的数的个数有 $1,5$ 于是我们就的 $p(6) = 2$，带入计算得到答案 我们输入一个 $T (1 <= T <= 10^6)$ 表示 $T$ 组输入， 然后对于每一组输入我们给定 $x (2 <= x <= 10^6)$ 的值和 $k (1 <= k <= 10^9)$ 的值，对于每一次询问输出 $F(x)$

Format

Input

第一行输入一个 $T \ (1 <= T <= 10^6)$ 表示 $T$ 组输入 第二行到第 $T+1$ 每行输入一个 $x,k \ (2 <= x <= 10^6,1 <= k <= 10^9)$

Output

输出 $F(x)$ 的值

Samples

2
2 4
999999 999999999

250000002
780227361

Limitation

1s, 1024KiB for each test case.