DIVFACT4 - 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


hide comments
DK...: 2019-03-15 23:39:56

Very nice problem, take care about all your variables. it could be overflow is some testcases, so take mod(m) all of them, this cost me several WA's

Min_25: 2015-07-27 18:37:22

@underchange
Please look at the constraints carefully.

underchange: 2015-07-27 11:25:30

@Min_25 I submitted my AC program for DIVFACT3 to DIVFACT4, but it get WA on input #1. Input #1: T ≤ 10^4, N ≤ 10^4, is even weaker than DIVFACT3. Is there something wrong with this input or this constraint?

[Lakshman]: 2015-05-18 18:50:01

Test cases are very strong, I have two different algorithm for which I got AC in DIVFACT3 in 1.4s here is giving WA.

Min_25: 2015-05-15 02:25:30

@Lakshman
- Input #1, #2, #3: WA
- Input #4, #5: TLE

[Lakshman]: 2015-05-14 07:09:36

@Min_25 Can you please help me, I am getting WA at First test Case But I Think my algorithm is correct.


Added by:Min_25
Date:2015-01-30
Time limit:1s-20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:DIVFACT