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;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
int bsr(int x) { return 31 - __builtin_clz(x); }
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class T>
T pow(T x, ll n) {
  T r = 1;
  while (n) {
    if (n & 1) r *= x;
    x *= x;
    n >>= 1;
  }
  return r;
}
template <uint MD>
struct ModInt {
  uint v;
  ModInt() : v{0} {}
  ModInt(ll v) : v{normS(v % MD + MD)} {}
  static uint normS(const uint &x) { return (x < MD) ? x : x - MD; };
  static ModInt make(const uint &x) {
    ModInt m;
    m.v = x;
    return m;
  }
  ModInt operator+(const ModInt &r) const { return make(normS(v + r.v)); }
  ModInt operator-(const ModInt &r) const { return make(normS(v + MD - r.v)); }
  ModInt operator*(const ModInt &r) const { return make((ull)v * r.v % MD); }
  ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
  ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
  ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
  static ModInt inv(const ModInt &x) { return pow(ModInt(x), MD - 2); }
};
using Mint = ModInt<TEN(9) + 7>;
const int MD = 1001001;
int factor[MD];
void first() {
  fill(begin(factor), end(factor), -1);
  for (int i = 2; i < MD; i++) {
    if (factor[i] != -1) continue;
    for (int j = i; j < MD; j += i) {
      factor[j] = i;
    }
  }
}
int main() {
  first();
  V<int> id2v[300];
  map<V<int>, int> vs;
  int id[MD];
  for (int i = 1; i < MD; i++) {
    map<int, int> mp;
    int x = i;
    while (factor[x] != -1) {
      mp[factor[x]]++;
      x /= factor[x];
    }
    V<int> v;
    for (auto p : mp) {
      v.push_back(p.second);
    }
    sort(begin(v), end(v));
    if (vs.count(v)) {
      id[i] = vs[v];
    } else {
      int nid = int(vs.size());
      vs[v] = nid;
      id[i] = nid;
      id2v[nid] = v;
    }
  }
  int C = vs.size();
  static Mint to1[MD][25], to0[MD][25];
  to0[0][0] = 1;
  for (int i = 1; i < 30; i++) {
    to1[0][i] = 1;
  }
  for (int i = 1; i < MD; i++) {
    Mint sm0, sm1;
    for (int j = 0; j < 25; j++) {
      sm0 += to0[i - 1][j];
      sm1 += to1[i - 1][j];
      to0[i][j] = sm0;
      to1[i][j] = sm1;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int r, n;
    scanf("%d %d", &r, &n);
    V<int> v = id2v[id[n]];
    Mint co[11];
    co[0] = 1;
    int nw = 1;
    for (int d : v) {
      for (int i = nw; i >= 0; i--) {
        co[i] = co[i] * to0[r][d];
        if (i) co[i] += co[i - 1] * to1[r][d];
      }
      nw++;
    }
    Mint ans = 0;
    for (int i = 0; i < 11; i++) {
      ans += co[i] * Mint(1 << i);
    }
    printf("%d\n", ans.v);
  }
  return 0;
}