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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeMap;
import java.util.HashMap;

public class E {
    public static void main(String args[]) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }

    static class Solver {
        final int MAXP = 20;
        final int MAXV = 1000000;
        final int MAXR = 1000000;
        final int MOD = 1000000007;

        int[][] g = new int[MAXP + 1][MAXR + 10];
        int[] nt = new int[MAXV + 10];
        public void solve(InputReader in, PrintWriter out) {
            preCalc();
            int q = in.readInt();
            //StringBuilder ans = new StringBuilder();
            while((q--) > 0) {
                int r = in.readInt(), n = in.readInt();
                long res = 1;
                HashMap <Integer,Integer> pr = new HashMap <Integer, Integer>();
                while (n > 1) {
                    int v = nt[n];
                    if (!pr.containsKey(v))
                        pr.put(v, 1);
                    else
                        pr.put(v, pr.get(v) + 1);
                    n /= v;
                }
                for(int u : pr.keySet()) {
                    int v = pr.get(u);
                    res = res * g[v][r] % MOD;
                }
                //ans.append(res + "\n");
                out.print(res + "\n");
            }
           // out.print(ans);
        }

        void preCalc() {
            g[0][0] = 1;
            for(int i=1; i<=MAXP; i++)
                g[i][0] = 2;
            int inv2 = power(2, MOD - 2);
            for(int r=1; r<=MAXR; r++) {
                g[0][r] = 1;
                for(int i=1; i<=MAXP; i++) {
                    g[i][r] = (g[i - 1][r] + g[i][r - 1]) % MOD;
                }
            }

            for(int i=0; i<=MAXV; i++)
                nt[i] = i;
            for(int i=2; i<=1000; i++)
            if (nt[i] == i) {
                for(int j=i*i; j<=MAXV; j+=i)
                    nt[j] = i;
            }
        }

        int power(int a, int n) {
            if (n == 0)
                return 1;
            int x = power(a, n / 2);
            x = (int)((long)x * x % MOD);
            if (n % 2 == 1)
                x = (int)((long)x * a % MOD);
            return x;
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public InputReader(File f) {
            try {
                reader = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                throw (new RuntimeException(e));
            }
        }

        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 int readInt() {
            return Integer.parseInt(next());
        }

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

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

        public String readLine() {
            String s = "";
            try {
                s = reader.readLine();
            } catch (IOException e) {
                throw (new RuntimeException(e));
            }
            return s;
        }
    }
}