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:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF757E extends PrintWriter {
	CF757E() { super(System.out); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF757E o = new CF757E(); o.main(); o.flush();
	}

	static final int N = 1000000, R = 1000000, MD = 1000000007;
	int[][] ee = new int[N + 1][7]; int[] kk = new int[N + 1];
	int[][] dp = new int[R + 1][20];
	void init() {
		for (int a = 2; a <= N; a++) {
			if (kk[a] != 0)
				continue;
			for (int b = a; b <= N; b += a) {
				int e = 0;
				for (int c = b; c % a == 0; c /= a)
					e++;
				ee[b][kk[b]++] = e;
			}
		}
		dp[0][0] = 1;
		for (int i = 1; i < 20; i++)
			dp[0][i] = 2;
		for (int r = 1; r <= R; r++) {
			dp[r][0] = 1;
			for (int i = 1; i < 20; i++)
				dp[r][i] = (dp[r][i - 1] + dp[r - 1][i]) % MD;
		}
	}
	void main() {
		init();
		int q = sc.nextInt();
		while (q-- > 0) {
			int r = sc.nextInt();
			int n = sc.nextInt();
			long ans = 1;
			for (int i = 0; i < kk[n]; i++)
				ans = (ans * dp[r][ee[n][i]]) % MD;
			println(ans);
		}
	}
}