描述

Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.

Bash defines a function $f_0(n)$, which denotes the number of ways of factoring $n$into two factors $p$ and $q$ such that $gcd(p, q) = 1$. In other words, $f_0(n)$ is the number of ordered pairs of positive integers $(p, q)$ such that $p·q = n$ and $gcd(p, q) = 1$.

But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where $f_r + 1$ is defined as: Where $(u, v)$ is any ordered pair of positive integers, they need not to be co-prime.

Now Bash wants to know the value of $f_r(n)$ for different $r$ and $n$. Since the value could be huge, he would like to know the value modulo $10^9 + 7.$ Help him!

中文题意

定义$f_0(n)$为 $pq=n$且 $(pq=1)$的$(pq)$对数。 定义： $q$次询问，每次回答$f_r(n)(mod 10^9+7)$. 数据范围： $n，r，q，\le 10^6$

输入

The first line contains an integer $q (1 ≤ q ≤ 10^6)$ — the number of values Bash wants to know.

Each of the next $q$ lines contain two integers $r$ and $n (0 ≤ r ≤ 10^6, 1 ≤ n ≤ 10^6),$ which denote Bash wants to know the value $f_r(n)$.

输出

Print $q$ integers. For each pair of $r$ and $n$ given, print $f_r(n)$ modulo $109^ + 7$ on a separate line.

样例

5
0 30
1 25
3 65
2 5
4 48

8
5
25
4
630