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.io.PrintStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
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 solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        static final int MAXN = (int) 1e6 + 1;
        static final int MAXLOGN = (int) (Math.log(MAXN) / Math.log(2)) + 2;
        static final double SQRTMAXN = Math.sqrt(MAXN);
        static final int NUM_PRIME = (int) (SQRTMAXN / Math.log10(SQRTMAXN)) + 100;
        static int[][] dp = new int[MAXN][MAXLOGN];
        static boolean[] isPrime = new boolean[MAXN];
        static int nprime;
        static int[] prime = new int[NUM_PRIME];
        int np;
        int[] lprime = new int[100];
        int[] lcnt = new int[100];

        static {
            dp[0][0] = 1;
            for (int i = 1; i < MAXLOGN; ++i) {
                dp[0][i] = 2;
            }

            for (int i = 1; i < MAXN; ++i) {
                dp[i][0] = 1;
                int sum = dp[i - 1][0];
                for (int j = 1; j < MAXLOGN; ++j) {
                    sum = Mod.addMod(sum, dp[i - 1][j]);
                    dp[i][j] = sum;
                }
            }

            Arrays.fill(isPrime, true);
            isPrime[0] = false;
            isPrime[1] = false;
            for (int i = 2; i < MAXN; ++i)
                if (isPrime[i]) {
                    int j = 2 * i;
                    while (j < MAXN) {
                        isPrime[j] = false;
                        j += i;
                    }
                }

            int sqrt = (int) Math.sqrt(MAXN) + 1;
            nprime = 0;
            for (int i = 2; i < sqrt; ++i)
                if (isPrime[i]) {
                    prime[nprime++] = i;
                }
            //System.err.println(nprime);
        }

        int calc(int n, int r) {
            if (n == 1) return 1;

            np = 0;
            for (int i = 0; i < nprime; ++i) {
                if (isPrime[n]) {
                    lprime[np] = n;
                    lcnt[np] = 1;
                    np++;
                    break;
                }
                if (n % prime[i] == 0) {
                    lprime[np] = prime[i];
                    lcnt[np] = 0;

                    while (n % prime[i] == 0) {
                        n /= prime[i];
                        lcnt[np]++;

                    }
                    np++;
                    if (n == 1) break;
                }
            }
            int re = 1;
            for (int i = 0; i < np; ++i) {
                re = Mod.mulMod(re, dp[r][lcnt[i]]);
            }
            return re;

        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int q = in.nextInt();
            for (int i = 0; i < q; ++i) {
                int r = in.nextInt();
                int n = in.nextInt();
                out.println(calc(n, r));
            }
            System.err.println("MAXLOGN " + MAXLOGN);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class Mod {
        public static final long MOD = 1000000007L;
        public static final boolean DEBUG = false;

        public static int addMod(int a, int b, long MOD) {
            if (DEBUG) return a + b;

            while (a < 0)
                a += MOD;
            while (b < 0)
                b += MOD;
            return (int) (((long) a + (long) b) % MOD);
        }

        public static int addMod(int a, int b) {
            return addMod(a, b, MOD);
        }

        public static int mulMod(int a, int b, long MOD) {
            if (DEBUG) return a * b;

            while (a < 0)
                a += MOD;
            while (b < 0)
                b += MOD;
            return (int) (((long) a) * ((long) b) % MOD);
        }

        public static int mulMod(int a, int b) {
            return mulMod(a, b, MOD);
        }

    }
}