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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:16777216")
using namespace std;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const long long LINF = INF * (long long)INF;
const int MOD = 1000 * 1000 * 1000 + 7;
const int MAX = 1000007;
int dil[MAX];
int p2[2 * MAX];
int f[2 * MAX];
int of[2 * MAX];
int n;
int mpow(long long num, int step) {
  long long res = 1;
  while (step) {
    if (step & 1) {
      res = (res * num) % MOD;
    }
    num = (num * num) % MOD;
    step /= 2;
  }
  return (int)res;
}
int q[50];
int nq;
long long ans;
int d, a;
int main() {
  f[0] = of[0] = p2[0] = 1;
  for (int i = (1); i < (2 * MAX); i++) {
    p2[i] = (p2[i - 1] * 2LL) % MOD;
    f[i] = (1LL * f[i - 1] * i) % MOD;
    of[i] = mpow(f[i], MOD - 2);
  }
  for (int i = (2); i < (MAX); i++) {
    if (!dil[i]) {
      for (int j = i; j < MAX; j += i) dil[j] = i;
    }
  }
  scanf("%d", &n);
  for (int i = (0); i < (n); i++) {
    scanf("%d%d", &d, &a);
    {
      nq = 0;
      long long ans = 1;
      int prev = 0, ct = 0, s = 0;
      while (a != 1) {
        s++;
        if (ct && dil[a] != prev) {
          q[nq++] = ct;
          ct = 0;
        }
        prev = dil[a];
        a /= dil[a];
        ct++;
      }
      if (ct != 0) q[nq++] = ct;
      if (!d)
        printf("%d\n", p2[nq]);
      else {
        for (int i = (0); i < (nq); i++) {
          long long add = 0;
          for (int addnum = (0); addnum < (q[i] + 1); addnum++) {
            long long CR = ans;
            CR = CR * f[d + addnum - 1] % MOD * of[addnum] % MOD;
            if (addnum != q[i]) {
              CR *= 2;
              if (CR > MOD) CR -= MOD;
            }
            add += CR;
          }
          add %= MOD;
          ans = (add * of[d - 1]) % MOD;
        }
        printf("%I64d\n", ans);
      }
    }
  }
}