SPOJ.com - Problem DIVFACT2

DIVFACT2 - Divisors of factorial (medium)

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

Submit solution!

hide comments

< Previous 1 2 Next >

	wisfaq: 2015-01-18 21:30:24 I'm still curious what the 'intermediate' method is. Can someone PM me at http://www.spoj.com/forum? --Francky--> I can write it to you ;-) And congrats again for taking again the rank#1 at DF3 ; edit(taken again by abdou_93)!!! Amazing !!! Last edit: 2015-01-18 23:07:00
	[Lakshman]: 2015-01-18 16:56:05 Yeh!! On the top. My method is faster for this but getting TLE in hard version. --Francky--> May I deduce that the complexity isn't the same? But you have a good constant, it's true. Last edit: 2015-01-18 17:13:41
	[Lakshman]: 2015-01-18 15:46:00 Thanks @Francky I got Accepted with the Intermediate version now I will explore the the faster one. --Francky--> Nice first step, I hope you'll enjoy the next one. Your persistence is admirable. Congrats for all your efforts. --Lakshman->Thanks @Francky. Last edit: 2015-01-18 16:00:57
	abdou_93: 2015-01-18 15:26:29 I can't find any idea edit: found it :D --Francky--> Nice, I hope you've enjoyed the steps. Congrats to you too for this first place. abdou--> Thanks :D Last edit: 2015-01-18 19:32:05
	[Lakshman]: 2015-01-18 14:32:28 @Francky I think I got the idea but wrong answer. --Francky--> You have that I called the 'intermediate' idea in DIVFACT3 ; you'll be able to get AC here if you find your bug(s) ; you'll need more ideas for DIVFACT3. Good luck ;-) Last edit: 2015-01-18 14:42:56
	Francky: 2015-01-18 14:10:35 Congrats to wisfaq as the first solver. --wisfaq--> Thanks. Last edit: 2015-01-18 14:17:08
	ivar.raknahs: 2015-01-18 09:06:16 We need a good algorithm.Well very hard constraints. --Francky--> It's not so hard to find the key once solved DIVFACT. Profile the code and find the bottleneck, two basic methods are to be used, nothing advanced. Last edit: 2015-01-18 11:14:28
	[Lakshman]: 2015-01-17 16:33:11 @Francky can you please have a look at my algorithm, what is the expected complexity? --ans--> You need a better one than the obvious solution for DIVFACT, I won't give more hints. Good luck. Last edit: 2015-01-18 01:54:42

Submit solution!

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