DIVFACT3  Divisors of factorial (hard)
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 < 5432 1 < N < 10^8 1 < M < 10^9
For N, M : uniform random input in the range.
One input file.
Information
As it is possible to solve DIVFACT2 with fast language and intermediate method, here is the hard edition.
Warning : It could be very hard or impossible to solve this problem with slow languages.
Time limit is approx ×4 my unoptimized C_time. Good luck and have fun ;) (Edit 20170211 ; TL updated ; compiler changes)
hide comments
pratham_1:
20170716 18:19:40
On codeChef onLine codecompile run , my code runs in 0.3s , here it says NZEC error , Any idea why?? same happened with DIVFACT2 , i used modified sieve still not working here:( 

r_ash:
20170505 05:34:55
can this be done by counting primes using segmented sieve? or some other algorithm is to be used?


Francky:
20170210 00:23:25
@Michael :


Michael Kharitonov:
20170207 21:03:31
Clang is much faster than GCC for my algorithm, maybe because GCC is much older.


mehmetin:
20150216 09:11:18
I solved the problem, but with a huge amount of memory and not with a really fast time. Can some hint or useful link be given about the prime count method mentioned below?


ISHANI:
20150130 09:08:57
I am very excited for the next version of DIVFACT(Min_25 do it fast).enjoyed solving it~~~~~.


:(:
20150127 10:24:24
@rohith... Thanks a ton for helping me out.. :) Last edit: 20150127 14:28:35 

Min_25:
20150122 11:53:16
I would like to propose a little different constraint such as (T < 5.432, N < 10^11 and M < 10^12).


Francky:
20150122 10:42:06
@Lakshman : Fine, very good. I was thinking at that problem again ; DF2 and DF3 are too near, I build them very quickly. I think setting an extreme edition, or change constraints here. As we don't like to change constraints, I think put DF3 in tutorial and set DF4 harder. The fact is almost everybody got the whole idea for DF2 and got AC for DF3 by the way (except one ;) ).


[Lakshman]:
20150122 09:13:18
@Francky. Yes it is possible with python(PYPY). 
Added by:  Francky 
Date:  20150118 
Time limit:  15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  DIVFACT2 