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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE_cf_af solver = new TaskE_cf_af();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE_cf_af {
        int[][] f;
        final long MOD = (long) 1e9 + 7;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            f = new int[30][1000001];
            ArrayUtils.fill(f, -1);
            int q = in.nextInt();
            for (int i = 0; i < 30; ++i) {
                for (int j = 0; j <= 1000000; ++j) {
                    if (j == 0) {
                        f[i][j] = 2;
                        continue;
                    }
                    if (i == 0) {
                        f[i][j] = 1;
                        continue;
                    }
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                    if (f[i][j] >= MOD) {
                        f[i][j] -= MOD;
                    }
                }
            }
            int[] primes = new int[1000001];
            primes[1] = 1;
            for (int i = 2; i <= 1000000; ++i) {
                if (primes[i] == 0) {
                    for (int j = i; j <= 1000000; j += i) {
                        primes[j] = i;
                    }
                }
            }
            while (q-- > 0) {
                int r = in.nextInt();
                int n = in.nextInt();
                long res = 1;

                while (n != 1) {
                    int cnt = 0, p = primes[n];
                    while (n % p == 0) {
                        n /= p;
                        cnt++;
                    }
                    res = (res * f[cnt][r]) % MOD;
                }
                out.println(res);
            }
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

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

    }

    static class ArrayUtils {
        public static void fill(int[][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                Arrays.fill(f[i], value);
            }
        }

    }
}