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;
long long readi() {
  long long input = 0;
  char c = ' ';
  while (c < '-') {
    c = getchar();
  }
  bool negative = false;
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  while (c >= '0') {
    input = 10 * input + (c - '0');
    c = getchar();
  }
  if (negative) {
    input = -input;
  }
  return input;
}
string reads() {
  string input = "";
  char c = ' ';
  while (c <= ' ') {
    c = getchar();
  }
  while (c > ' ') {
    input += c;
    c = getchar();
  }
  return input;
}
void printi(long long output) {
  if (output == 0) {
    putchar('0');
    return;
  }
  if (output < 0) {
    putchar('-');
    output = -output;
  }
  vector<char> vout;
  while (output) {
    vout.push_back((output % 10) + '0');
    output /= 10;
  }
  for (int i = vout.size() - 1; i >= 0; i--) {
    putchar(vout[i]);
  }
  return;
}
void prints(string output) {
  for (int i = 0; i < output.length(); i++) {
    putchar(output[i]);
  }
  return;
}
bool prime[1000010];
int T, K;
int id[1000010];
int f[1000010][20];
vector<int> primes;
vector<int> cnt;
int32_t main() {
  if (fopen("cf757e.in", "r")) {
    freopen("cf757e.in", "r", stdin);
    freopen("cf757e.out", "w", stdout);
  }
  for (int i = 2; i < 1000010; i++) {
    prime[i] = true;
  }
  for (long long i = 2; i < 1000010; i++) {
    if (!prime[i]) {
      continue;
    }
    for (long long j = i * i; j < 1000010; j += i) {
      prime[j] = false;
    }
    primes.push_back(i);
  }
  f[0][0] = 1;
  for (int i = 1; i < 20; i++) {
    f[0][i] = 2;
  }
  for (int i = 1; i < 1000010; i++) {
    for (int j = 0; j < 20; j++) {
      for (int k = 0; k <= j; k++) {
        f[i][j] += f[i - 1][k];
        f[i][j] %= 1000000007;
      }
    }
  }
  T = readi();
  while (T--) {
    int a, b, rem;
    a = readi();
    b = readi();
    if (b == 1) {
      putchar('1');
      putchar('\n');
      continue;
    }
    rem = b;
    cnt.clear();
    for (int i = 0; i < primes.size(); i++) {
      int p = primes[i];
      if (p * p > b) {
        break;
      }
      if (rem % p) {
        continue;
      }
      int num = 0;
      while (rem % p == 0) {
        rem /= p;
        num++;
      }
      cnt.push_back(num);
    }
    if (rem != 1) {
      cnt.push_back(1);
    }
    long long ans = 1ll;
    for (int i = 0; i < cnt.size(); i++) {
      ans *= f[a][cnt[i]];
      ans %= 1000000007;
    }
    printi(ans);
    putchar('\n');
  }
}