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 final class bash_and_functions
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static long[][] dp;
	static long mod=(long)(1e9+7);
	static int maxn=(int)(1e6)+1;
	static int[] sp;
	static Map<Integer,Integer> m1=new HashMap<>();
	
	static void mark(int num)
	{
		int i=2,elem;
		while((elem=(num*i))<maxn)
		{
			i++;sp[elem]=num;
		}
	}
	
	static void build()
	{
		sp=new int[maxn];
		for(int i=2;i<maxn;i++)
		{
			if(sp[i]==0)
			{
				sp[i]=i;mark(i);
			}
		}
	}
	
	static void put(int idx,int val)
	{
		if(m1.get(idx)==null)
		{
			m1.put(idx,val);
		}
		else
		{
			m1.put(idx,m1.get(idx)+val);
		}
	}
	
    public static void main(String args[]) throws Exception
    {
		build();dp=new long[21][maxn];dp[0][0]=1;
		for(int i=1;i<=20;i++)
		{
			dp[i][0]=2;
		}
		for(int i=1;i<maxn;i++)
		{
			for(int j=0;j<=20;j++)
			{
				if(j==0)
				{
					dp[j][i]=1;continue;
				}
				dp[j][i]=(dp[j-1][i]+dp[j][i-1])%mod;
			}
		}
		for(int i=0;i<maxn;i++)
		{
			for(int j=1;j<21;j++)
			{
				dp[j][i]=(dp[j-1][i]+dp[j][i])%mod;
			}
		}
		int q=sc.nextInt();
		while(q>0)
		{
			int r=sc.nextInt(),n=sc.nextInt();
			if(n==1)
			{
				out.println(1);
			}
			else if(r==0)
			{
				m1=new HashMap<>();int curr=n;
				while(curr>1)
				{
					put(sp[curr],1);curr/=sp[curr];
				}
				out.println(1L<<(m1.size()));
			}
			else
			{
				m1=new HashMap<>();int curr=n;
				while(curr>1)
				{
					put(sp[curr],1);curr/=sp[curr];
				}
				long res=1;
				for(Map.Entry<Integer,Integer> en:m1.entrySet())
				{
					int now=en.getValue();long curr1=dp[now][r-1];
					res=(res*curr1)%mod;
				}
				out.println(res);
			}
			q--;
		}
		out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}