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 = 1e9 + 7;
const long long LL_INF = 1ll * INF * INF;
const int MAX_N = 1000000 + 7;
const int mod = INF;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
class Prime {
 public:
  static const int MAXN = 1e6 + 7;
  int primes[MAXN];
  int last[MAXN];
  int rev[MAXN];
  int num_primes = 0;
  Prime() { init(); }
  void sieve() {
    for (int i = 2; i < MAXN; ++i) {
      if (last[i] == 0) {
        last[i] = i;
        rev[i] = num_primes;
        primes[num_primes++] = i;
      }
      for (int j = 0;
           j < num_primes && primes[j] <= last[i] && primes[j] * i < MAXN;
           ++j) {
        last[i * primes[j]] = primes[j];
      }
    }
  }
  void init() {
    num_primes = 0;
    sieve();
  }
  int operator[](const int& pos) const { return primes[pos]; }
  int size() const { return num_primes; }
  bool is_prime(int x) const { return last[x] == x; }
  int count_divisiors(int num) {
    if (is_prime(num)) return 2;
    auto factors = get_factors(num);
    int res = 1;
    for (auto& p : factors) {
      res *= p.second;
    }
    return res;
  }
  int distinct_factors(int num) { return (int)get_factors(num).size(); }
  vector<pair<int, int>> get_factors(int num) {
    vector<pair<int, int>> res;
    while (num > 1) {
      int cnt = 0, prev = last[num];
      while (last[num] == prev) {
        num /= prev;
        ++cnt;
      }
      res.push_back({prev, cnt});
    }
    return res;
  }
  static long long count_in_factorial(long long prime, long long n) {
    long long res = n / prime;
    long long x = prime;
    const auto limit = n / prime;
    do {
      x *= prime;
      res += n / x;
    } while (x <= limit);
    return res;
  }
} prime;
int calc(int r, int n) {
  if (!r) return (1 << prime.get_factors(n).size());
  int sum = 0;
  for (int i = 1; i <= n; ++i)
    if (n % i == 0) sum += calc(r - 1, i);
  return sum;
}
const int M = 20;
int pre_calc[MAX_N][M];
int sum[MAX_N][M];
int one_calc(int r, int n) {
  auto p = prime.get_factors(n);
  if (!r) {
    return (1 << p.size());
  } else {
    long long res = 1;
    for (auto temp : p) {
      res = res * pre_calc[r][temp.second] % mod;
    }
    return res;
  }
}
void solve() {
  for (int i = 1; i < MAX_N; ++i) {
    for (int j = 0; j < M; ++j) {
      if (i == 1) {
        pre_calc[i][j] = 2 * j + 1;
      } else {
        if (j == 0)
          pre_calc[i][j] = pre_calc[i - 1][j];
        else {
          pre_calc[i][j] = (pre_calc[i][j - 1] + pre_calc[i - 1][j]) % mod;
        }
      }
    }
  }
  int q;
  cin >> q;
  while (q-- > 0) {
    int r, n;
    cin >> r >> n;
    cout << one_calc(r, n) << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}