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 long double PI = acos(-1.0);
const long long LINF = (long long)1e18 + 5;
const int INF = (int)1e9 + 5;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
long long round(T x) {
  return x < 0 ? x - 0.5 : x + 0.5;
}
template <class T>
bool chmin(T& x, const T& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& x, const T& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const pair<P, Q>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool was = false;
  os << "{";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  bool was = false;
  os << "{";
  for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  bool was = false;
  os << "{";
  for (typename multiset<T>::const_iterator it = v.begin(); it != v.end();
       it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const map<P, Q>& v) {
  bool was = false;
  os << "{";
  for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
string nextToken() {
  static char str[(int)1e6 + 5];
  scanf("%s", str);
  return str;
}
template <class T>
T nextInt() {
  long long x = 0;
  bool p = false;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return (p ? -x : x);
}
const int P = (int)1e9 + 7;
const int INV_2 = (P + 1) / 2;
int mul(int x, int y) { return (long long)x * y % P; }
void add(int& x, int y) {
  x += y;
  if (x >= P) x -= P;
}
const int N = (int)1e6 + 100;
const int ALPHA = 22;
vector<int>* alphas = new vector<int>[N];
int sieve[N];
int C[N][ALPHA];
void calcC() {
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
  }
  for (int j = 1; j < ALPHA; j++) {
    C[0][j] = 0;
  }
  for (int i = 1; i < N; i++) {
    for (int j = 1; j < ALPHA; j++) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      if (C[i][j] >= P) C[i][j] -= P;
    }
  }
}
void calcSieve() {
  for (int p = 2; p < N; p++) {
    if (sieve[p] == 0) {
      for (int x = p; x < N; x += p) {
        sieve[x] = p;
      }
    }
  }
  for (int i = 2; i < N; i++) {
    int x = i;
    while (x != 1) {
      int p = sieve[x];
      int cnt = 0;
      while (x % p == 0) {
        ++cnt;
        x /= p;
      }
      alphas[i].push_back(cnt);
    }
    sort((alphas[i]).begin(), (alphas[i]).end());
  }
}
map<pair<vector<int>, int>, int> memo;
int foo(int alpha, int r) { return C[r + alpha - 1][alpha]; }
int query(int r, int n) {
  int res = 1;
  const vector<int>& alpha = alphas[n];
  int alphaLen = (int)alpha.size();
  for (int pos = 0; pos < alphaLen; pos++) {
    int x = alpha[pos];
    int prod = (1LL * foo(x - 1, r + 1) * 2 + foo(x, r)) % P;
    res = mul(res, prod);
  }
  return res;
}
void solve() {
  calcSieve();
  calcC();
  int q = nextInt<int>();
  while (q--) {
    int r, n;
    r = nextInt<int>();
    n = nextInt<int>();
    printf("%d\n", query(r, n));
  }
}
int main(int argc, char* argv[]) {
  srand(time(0));
  int t = 1;
  while (t--) {
    solve();
  }
}