Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

combinatorics

dp

number theory

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Bash Plays with Functions

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBash 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 *f*_{0}(*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, *f*_{0}(*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 *f*_{r + 1} is defined as:

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 *f*_{r}(*n*) for different *r* and *n*. Since the value could be huge, he would like to know the value modulo 10^{9} + 7. Help him!

Input

The first line contains an integer *q* (1 ≤ *q* ≤ 10^{6}) — the number of values Bash wants to know.

Each of the next *q* lines contain two integers *r* and *n* (0 ≤ *r* ≤ 10^{6}, 1 ≤ *n* ≤ 10^{6}), which denote Bash wants to know the value *f*_{r}(*n*).

Output

Print *q* integers. For each pair of *r* and *n* given, print *f*_{r}(*n*) modulo 10^{9} + 7 on a separate line.

Example

Input

5

0 30

1 25

3 65

2 5

4 48

Output

8

5

25

4

630

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2024 11:44:43 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|