#DIVFACT4. Divisors of factorial (extreme)

Divisors of factorial (extreme)

Find the number of divisors of N! (factorial) very fast !

Input

The first line contains an integer T, the number of test cases.

Each line of the next T lines contains two integers N and M.

Output

For each line, output a single line containing the number of divisors of N! modulo M.

Example

Input

3
10 989
10000 999989
10000000000 999999999989

Output

270
616797
40946947081

Constraints

1 ≤ T ≤ 104
0 ≤ N ≤ 1011
1 ≤ M ≤ 1012

Information

There are 5 input files.

- Input #1: T ≤ 104, N ≤ 104, TL = 1s

- Input #2: T ≤ 5, N ≤ 108, TL = 20s

- Input #3: T ≤ 5, N ≤ 109, TL = 20s

- Input #4: T ≤ 5, N ≤ 1010, TL = 20s

- Input #5: T ≤ 5, N ≤ 1011, TL = 20s

My total running time is 3.14 sec. (C++)

Credits