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 int N = 1e6;
const int MOD = 1e9 + 7;
struct Primes {
  vector<int> lp, pr;
  int n;
  Primes(int n) : n(n), lp(n + 1) {
    for (int i = 2; 1ll * i * i <= n; i == 2 ? i += 1 : i += 2) {
      if (lp[i] == 0) {
        for (long long j = 1ll * i * i; j <= n; j += i) {
          lp[j] = i;
        }
      }
    }
  }
} P(N);
struct Sums {
  vector<int> s;
  Sums(int n) : s(n + 1) {}
  void Set(int i, int x) { s[1 + i] = x; }
  void Compute() {
    for (int(i) = (0); (i) < ((int)s.size() - 1); (i)++)
      s[1 + i] = ((s[1 + i] + s[1 + i - 1]) % MOD);
  }
  int Get(int l, int r) {
    if (l > r) return 0;
    return ((s[1 + r] - s[1 + l - 1]) % MOD);
  }
  void Clear() { s.assign(s.size(), 0); }
};
const int MAXX = 20;
int F[N + 1][MAXX + 1];
int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0);
  Sums prv(MAXX + 1), nxt(MAXX + 1);
  for (int(r) = (0); (r) < (N + 1); (r)++) {
    for (int(i) = (0); (i) < (MAXX + 1); (i)++) {
      if (i == 0) {
        F[r][i] = 1;
      } else if (r == 0) {
        F[r][i] = 2;
      } else {
        F[r][i] = ((F[r][i - 1] + F[r - 1][i]) % MOD);
      }
    }
  }
  int q;
  scanf("%d", &q);
  for (int(Q) = (0); (Q) < (q); (Q)++) {
    int n, r;
    scanf("%d%d", &r, &n);
    int ans = 1;
    for (; n != 1;) {
      int c;
      int p = P.lp[n];
      if (p == 0) {
        c = 1;
        n = 1;
      } else {
        c = 0;
        for (; n % p == 0; n /= p, c++)
          ;
      }
      ans = ((ans * 1ll * F[r][c]) % MOD);
    }
    printf("%d\n", ans);
  }
  return 0;
}