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;
int pd[1111111], p2[1111111];
vector<int> pf[1111111], pc[1111111];
int fac[2111111], ifac[2111111];
int power(int base, long long exponent) {
  int result = 1, m = base;
  while (exponent) {
    if (exponent & 1) result = ((long long)result * m) % 1000000007;
    m = ((long long)m * m) % 1000000007;
    exponent /= 2;
  }
  return result;
}
int c(int n, int k) {
  return (((long long)fac[n] * ifac[k]) % 1000000007 * ifac[n - k]) %
         1000000007;
}
int main(int argc, char *argv[]) {
  fac[0] = 1;
  for (int i = 0; i < (2111111); i++)
    fac[i + 1] = ((long long)fac[i] * (i + 1)) % 1000000007;
  ifac[2111111 - 1] = power(fac[2111111 - 1], 1000000007 - 2);
  for (int i = (2111111 - 2); i >= (0); i--)
    ifac[i] = ((long long)ifac[i + 1] * (i + 1)) % 1000000007;
  for (int i = 2; i < 1111111; ++i)
    if (!pd[i]) {
      for (int j = i; j < 1111111; j += i) {
        pd[j]++;
        int tmp = j / i;
        pc[j].push_back(1);
        while (tmp % i == 0) {
          pc[j][pd[j] - 1]++;
          tmp /= i;
        }
      }
    }
  p2[0] = 1;
  for (int i = 0; i < (1111111 - 1); i++) p2[i + 1] = (2 * p2[i]) % 1000000007;
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int R, N;
    scanf("%d%d", &R, &N);
    int ans = 0;
    if (!R)
      ans = p2[pd[N]];
    else {
      ans = 1;
      for (int i = 0; i < (pd[N]); i++) {
        int tmp = 0;
        for (int j = (0); j <= (pc[N][i]); j++)
          tmp = (tmp + c(j + R - 1, R - 1) * (1LL + (j != pc[N][i]))) %
                1000000007;
        ans = ((long long)ans * tmp) % 1000000007;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}