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 INF = (int)2e9;
const long long INFL = (long long)9e18;
const int MAXINT = ((~0) ^ (1 << 31));
const long long MAXLL = ((~0) ^ ((long long)1 << 63));
template <class T>
inline T pow2(T a) {
  return a * a;
}
template <class T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, true) : false;
}
template <class T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, true) : false;
}
const int maxn = 1e6 + 100;
const int MOD = 1e9 + 7;
int c[maxn][25], csum[maxn][25];
int dv[maxn];
int main() {
  for (int i = 2; i < maxn; i++) {
    if (dv[i] == 0) {
      for (int j = i; j < maxn; j += i) dv[j] = i;
    }
  }
  for (int i = 0; i < (int)(maxn); i++) {
    int lim = min(i + 1, 25);
    for (int j = 0; j < (int)(lim); j++) {
      if (i == 0 || j == 0) {
        c[i][j] = 1;
        csum[i][j] = 1;
      } else {
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        csum[i][j] = (c[i][j] + csum[i - 1][j - 1]) % MOD;
      }
    }
  }
  pair<vector<int>, int> lastp;
  int lastans;
  int q;
  cin >> q;
  for (int i = 0; i < (int)(q); i++) {
    int lvl, num;
    scanf("%d %d", &lvl, &num);
    long long r = lvl;
    vector<int> v;
    int last = -1;
    while (num > 1) {
      if (dv[num] != last) v.push_back(0);
      last = dv[num];
      v.back()++;
      num /= dv[num];
    }
    if (lvl == 0) {
      printf("%d\n", (1 << v.size()));
      continue;
    }
    if (make_pair(v, lvl) == lastp) {
      printf("%d\n", lastans);
      continue;
    }
    long long res = 1;
    for (long long i = 0; i < v.size(); i++) {
      long long k = v[i];
      long long w = c[r + k][k] - c[r + k - 1][k];
      if (w < 0) {
        w += MOD;
      }
      long long p = (2 * w) % MOD;
      p += c[r + k - 1][k];
      p %= MOD;
      res *= p;
      res %= MOD;
    }
    printf("%d\n", res);
  }
}