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 ≤ 10^{4}
0 ≤ N ≤ 10^{11}
1 ≤ M ≤ 10^{12}
Information
There are 5 input files.
 Input #1: T ≤ 10^{4}, N ≤ 10^{4}, TL = 1s
 Input #2: T ≤ 5, N ≤ 10^{8}, TL = 20s
 Input #3: T ≤ 5, N ≤ 10^{9}, TL = 20s
 Input #4: T ≤ 5, N ≤ 10^{10}, TL = 20s
 Input #5: T ≤ 5, N ≤ 10^{11}, TL = 20s
My total running time is 3.14 sec. (C++)
Credits
 ivar.raknahs  the original problem (DIVFACT) author
 Francky  the author of DIVFACT2 and DIVFACT3
hide comments
Min_25:
20150727 18:37:22
@underchange


underchange:
20150727 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]:
20150518 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:
20150515 02:25:30
@Lakshman


[Lakshman]:
20150514 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:  20150130 
Time limit:  1s20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  DIVFACT 