Problem: 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 f0(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, f0(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 fr + 1 is defined as:

<image>

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 fr(n) for different r and n. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him!

Input

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

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

Output

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

Example

Input

5
0 30
1 25
3 65
2 5
4 48


Output

8
5
25
4
630

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;

public class E {
	public static void main(String[] args) throws IOException {

		/**/
		//Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		/*/
		//Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(new FileInputStream("src/e.in"))));
		BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("src/e.in")));
		/**/
		
		int MOD = 1000000007;
		int[][] pascal = new int[20][1000001];
		for (int i = 0; i <= 1000000; i++)
			pascal[0][i] = 1;
		for (int i = 1; i < 20; i++)
			pascal[i][0] = 2;
		for (int i = 1; i < 20; i++) {
			for (int j = 1; j <= 1000000; j++) {
				pascal[i][j] = (pascal[i][j-1]+pascal[i-1][j])%MOD;
			}
		}
		int[] sieve = new int[1000001];
		for (int i = 2; i <= 1000; i++) {
			if (sieve[i] == 0) {
				for (int j = i*i; j <= 1000000; j+=i) {
					sieve[j] = i;
				}
			}
		}
		StringBuilder ans = new StringBuilder();
		int q = Integer.parseInt(br.readLine());
		for (int z = 0; z < q; z++) {
			String[] split = br.readLine().split(" ");
			int r = Integer.parseInt(split[0]);
			int n = Integer.parseInt(split[1]);
			long temp = 1;
			HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();
			while (sieve[n] != 0) {
				int c = sieve[n];
				if (!counts.containsKey(c))
					counts.put(c, 1);
				else
					counts.put(c, counts.get(c)+1);
				n /= c;
			}
			if (n != 1) {
				int c = n;
				if (!counts.containsKey(c))
					counts.put(c, 1);
				else
					counts.put(c, counts.get(c)+1);
			}
			for (int c : counts.keySet()) {
				int count = counts.get(c);
				temp *= pascal[count][r];
				temp %= MOD;
			}
			ans.append(temp+"\n");
		}
		System.out.print(ans);
	}
}