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₀(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₀(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:

$\text{[math]}$

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⁹ + 7. Help him!

Input

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

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

Output

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

#	Name	Rating↕	Solved↕
1957E	Carousel of Combinations brute force combinatorics dp math number theory	2400	1.7k
1780F	Three Chairs bitmasks brute force combinatorics data structures dp number theory sortings	2300	2k
757E	Bash Plays with Functions brute force combinatorics dp number theory	2500	1.6k
401D	Roman and Numbers bitmasks brute force combinatorics dp number theory	2000	4.7k

Problemset