巴什在成为最伟大的神奇宝贝大师的旅程中感到疲倦。所以他决定休息一下,玩玩函数。
Bash 定义了一个函数 f0(n),它表示将 n 分解为两个因子 p 和 q 使得 gcd(p, q) = 1 的方式数。换句话说,f0(n) 是使得 p·q = n 且 gcd(p, q) = 1 的正整数 (p, q) 有序对的数量。
但 Bash 觉得计算这个函数太容易了。于是他定义了一系列函数,其中fr+1定义为:
$$f_{r+1}(n) = \sum_{u\cdot v=n} \frac{f_r(u) + f_r(v)}{2},$$
其中 (u, v) 是任意有序的正整数对,它们不必是互质的。
现在 Bash 想知道不同 r 和 n 的 fr(n) 值。由于该值可能很大,他想知道模 109 + 7 的值。帮助他!
输入
第一行包含一个整数 q (1 ≤ q ≤ 106) — Bash 想知道的值的数量。
接下来的 q 行包含两个整数 r 和 n (0 ≤ r ≤ 106, 1 ≤ n ≤ 106),这表示 Bash 想知道值 fr(n)。
输出
打印 q 个整数。对于给定的每一对 r 和 n,在单独的行上打印 fr(n) 模 109 + 7。
示例
输入 #1
5 0 30 1 25 3 65 2 5 4 48
输出 #1
8 5 25 4 630