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.*;

public class Main {

	public static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32765);
			tokenizer = null;
		}

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(System.in), 32765);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public char nextChar() {
			return next().charAt(0);
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public Integer[] nextIntegerArr(int n) {
			Integer[] arr = new Integer[n];
			for (int i = 0; i < n; i++) {
				arr[i] = new Integer(this.nextInt());
			}
			return arr;
		}

		public int[][] next2DIntArr(int n, int m) {
			int[][] arr = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					arr[i][j] = this.nextInt();
				}
			}
			return arr;
		}

		public int[] nextSortedIntArr(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			Arrays.sort(arr);
			return arr;
		}

		public long[] nextLongArr(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public long[] nextSortedLongArr(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			Arrays.sort(arr);
			return arr;
		}

		public char[] nextCharArr(int n) {
			char[] arr = new char[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextChar();
			}
			return arr;
		}
	}

	public static InputReader scn = new InputReader();
	public static PrintWriter out = new PrintWriter(System.out);

	public static int mod = (int) 1e9 + 7;
	public static int[] sieve = new int[(int) 1e6 + 1];
	public static long[][] dp = new long[(int) 1e6 + 1][21];

	public static void main(String[] args) {
		// InputStream inputStream = System.in; // Useful when taking input other than
		// console eg file handling // check ctor of inputReader
		// To print in file use this:- out = new PrintWriter("destination of file
		// including extension");

		for (int i = 1; i <= 1e6; i++) {
			sieve[i] = i;
		}
		for (int i = 2; i <= 1e6; i++) {
			if (sieve[i] == i) {
				for (int j = i; j <= 1e6; j += i) {
					sieve[j] = i;
				}
			}
		}

		dp[0][0] = 1;
		for (int r = 0; r <= 1e6; r++) {
			for (int k = 0; k <= 20; k++) {
				if (r == 0 && k == 0) {

				} else if (k == 0) {
					dp[r][k] = 1;
				} else if (r == 0) {
					dp[r][k] = 2;
				} else {
					dp[r][k] = dp[r - 1][k] + dp[r][k - 1];
					if (dp[r][k] >= mod) {
						dp[r][k] %= mod;
					}
				}
			}
		}

		int q = scn.nextInt();

		while (q-- > 0) {
			int r = scn.nextInt(), n = scn.nextInt();
			long ans = find(r, n);
			out.println(ans);
		}

		out.close();
	}

	public static long find(int r, int n) {
		long rv = 1;
		while (sieve[n] != 1) {
			int k = 0, x = sieve[n];
			while (n % x == 0) {
				n /= x;
				k++;
			}
			rv *= dp[r][k];
			if (rv >= mod) {
				rv %= mod;
			}
		}
		return rv;
	}
}