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 MAXN = 1500000;
int fac[MAXN], invfac[MAXN], P[MAXN];
const int MOD = 1000000007;
void mult(int &a, long long b) {
  a = (a * b) % MOD;
  if (a < 0) a += MOD;
}
int modex(int a, int p) {
  if (!p) return 1;
  if (p & 1) return ((long long)a * modex(a, p - 1)) % MOD;
  long long v = modex(a, p >> 1);
  return (v * v) % MOD;
}
int choose(int a, int b) {
  if (b > a) return 0;
  int ret = fac[a];
  mult(ret, invfac[b]);
  mult(ret, invfac[a - b]);
  return ret;
}
int main() {
  for (int i = 1; i < MAXN; ++i) P[i] = i;
  for (int i = 2; i < MAXN; ++i)
    if (P[i] == i)
      for (int j = i + i; j < MAXN; j += i) P[j] = i;
  fac[0] = invfac[0] = 1;
  for (int i = 1; i < MAXN; ++i) {
    fac[i] = fac[i - 1];
    mult(fac[i], i);
    invfac[i] = modex(fac[i], MOD - 2);
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int r, n;
    scanf("%d%d", &r, &n);
    int ans = 1;
    while (n > 1) {
      int p = P[n];
      int d = 0;
      while (n % p == 0) {
        ++d;
        n /= p;
      }
      mult(ans, 2 * choose(d + r, d) - choose(d + r - 1, d));
    }
    printf("%d\n", ans);
  }
}