DIVFACT3 - Divisors of factorial (hard)

no tags 

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 2017-02-11 ; TL updated ; compiler changes)


hide comments
abdou_93: 2015-01-19 18:22:57

@Robert Gerbicz Amazing speed!.congratulation :D

Francky: 2015-01-19 14:33:37

Congrats to Robert Gerbicz for the new rank#1 (and at first attempt).
(gerrob)Thanks!

Last edit: 2015-01-19 14:50:07
[Lakshman]: 2015-01-19 08:52:03

My algorithm can be much faster If I can make (s******ing) in constant time. I think I can.
--Franck--> It's true, a small formula for approximation and it can be done ;-). Congrats again.

Last edit: 2015-01-19 09:00:58
abdou_93: 2015-01-18 19:42:24

@Francky : do you have another idea ?
--Francky--> You got the main idea and correct complexity, after I can see only some nice little optis. I would like to share, but I don't think it's a good idea.

abdou--> OK. thanks alot Francky :D (Y)

Last edit: 2015-01-18 20:32:15
Francky: 2015-01-18 14:12:35

Congrats to wisfaq as the first solver.

--wisfaq--> Thanks.

Last edit: 2015-01-18 14:21:42

Added by:Francky
Date:2015-01-18
Time limit:15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:DIVFACT2