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>
using namespace std;
const long long UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
long long mod_pow(long long a, long long n, long long mod) {
  long long ret = 1;
  long long p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
const long long MAXN = 1e6 + 4;
const long long MAXP = MAXN;
bool sieve_array[MAXP + 1];
long long sp[MAXP + 1];
void sieve() {
  for (long long i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    sp[i] = INF;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  long long lim = sqrt(MAXP) + 1;
  for (long long i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (long long j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        chkmin(sp[j], i);
      }
    }
  }
  for (long long i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      chkmin(sp[i], i);
    }
  }
}
map<long long, long long> factorize(long long x) {
  map<long long, long long> h;
  while (x > 1) {
    long long p = sp[x];
    x /= p;
    h[p]++;
  }
  if (x > 1) h[x]++;
  return h;
}
const long long mn = 1e6 + 2, me = 21;
long long f[mn][me];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  f[0][0] = 1;
  for (long long e = 1; e < me; e++) f[0][e] = 2;
  for (long long n = 1; n < mn; n++) {
    long long sum = 0;
    for (long long e = 0; e < me; e++) {
      sum = (sum + f[n - 1][e]) % 1000000007LL;
      f[n][e] = sum;
    }
  }
  sieve();
  long long q;
  scanf("%lld", &q);
  for (long long ii = 0; ii < q; ii++) {
    long long n, r;
    scanf("%lld%lld", &r, &n);
    map<long long, long long> h = factorize(n);
    long long ans = 1;
    for (auto &w : h) {
      ans = (ans * f[r][w.second]) % 1000000007LL;
    }
    printf("%lld\n", ans);
  }
}