DIVFACT2  Divisors of factorial (medium)
Factorial numbers are getting big very soon, you'll have to compute the number of divisors of such highly composite numbers.
Input
The first line contains an integer T, the number of test cases.
On the next T lines, you will be given two integers N and M.
Output
Output T lines, one for each test case, with the number of divisors of the factorial of N.
Since the answer can get very big, output it modulo M.
Example
Input: 3 2 1000 3 11 4 5 Output: 2 4 3
Constraints
0 < T < 512 1 < N < 10^8 1 < M < 10^9
For N, M : uniform random input in the range.
One input file.
Information
Time limit is sqrt(T_good.py × T_bad.c).
It implies that you can solve it with some interpreted languages with correct algorithm without any optis, but will get TLE with fast languages and non optimal algorithm.
Good luck and have fun ;)
(Edit 20170211 : TL updated ; compiler changes)
hide comments
pratham_1:
20170716 11:53:18
Any hints for this problem ?? i give up 

surya2196:
20160403 16:22:52
@francky can you plese provide some test case


shivucoder55:
20160318 21:05:25
I solved by precomputing all prime numbers less than 10^8 then determining no. of divisors but still getting TLE ....


shikhar jindal:
20160317 17:26:38
not getting any idea how to solve this :( ...what other concepts are needed along with the lagrange's theorem..thanks in advance :)


Maroof:
20150608 12:17:34
Why this problem isn't showing on the list of solved problems? .. BTW awesome problem. Learnt a lot of things to optimize the code :)


Sayak Haldar:
20150211 14:08:11
Francky, would I get an AC if I precompute all the prime nos less than 10^8 then use (n)1/2(logn) per query?


Francky:
20150130 17:41:09
Now there's DIVFACT4, it's time to move this one to tutorial, as almost every submission got AC with both (DF2, DF3) without any change.


rohith:
20150124 12:19:43
@Francky my code works absolutely fine but still WA


[Lakshman]:
20150119 07:58:25
Enjoying this!! Getting closer to abdou_93 Trying for first place..........Taken first place!!!


wisfaq:
20150118 21:30:24
I'm still curious what the 'intermediate' method is.

Added by:  Francky 
Date:  20150117 
Time limit:  5.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  DIVFACT 