EASYFACT - Easy Factorials

Finding factorials are easy but they become large quickly that is why Lucky hate factorials. Today he have another task related to factorials.

For a given number n how many ways factorial n can expressed as a sum of two or more consecutive positive integers. Can you help lucky ?

Input

First line contains single integer T < 5001, next T lines followed by an integer N<10^8 and M<10^9.

where M is a prime number.

Output

Print the desired result mod M.

Example

Input:
1
3 7

Output:
1

Explanation:: 3! = 1+2+3 only one way.

Speed Adicts My best time for all cases is 1.57s. Best of Luck have fun:) .


Added by:[Lakshman]
Date:2015-05-13
Time limit:5s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2017-02-07 21:46:03 Michael Kharitonov
Lakshman, I've beaten your time:) This problem is quite similar to DIVFACT3

==(Lakshman)==>Congrats "Michael Kharitonov" your code is quite fast, With new Cluster My old code runs in .96s.

Last edit: 2017-02-08 07:16:13
2016-10-26 23:09:04 Sifat Shishir
Got AC :)

Last edit: 2016-10-27 17:48:04
2016-07-13 08:08:14
now it is working up n<=10^6 and then TLE shit man :(

=(Lakshman)=>Some suggestion 1. Do not compute prime every time just precompute once and use it.

Last edit: 2016-07-14 05:31:51
2016-07-06 06:54:56
i can't understand why it is showing WA Admin can u check it out for me id 17232977


==(Lakshman)=>Because your solution is wrong.

Last edit: 2016-07-06 17:51:53
2016-02-05 14:38:04 varun bumb
FINALLY, GREEN!!
Took 6 months to figure out the mistake
BTW, Awesome Problem.
Advice: Try to minimize the use of long long and mod


==>Good Job.

Last edit: 2016-02-08 05:52:22
2015-10-31 21:43:48 varun bumb
@[Lakshman] : Now my code is working fine for small inputs as well still i'm getting WA. Can you check my code. Code id: 15518033
2015-09-02 19:40:56 Pranav Rai
@admin I am getting a TLE - Can you suggest any improvements - http://www.spoj.com/submit/EASYFACT/id=14918201
2015-09-01 17:48:40 Arjav
@Admin after too much struggle my solution get ac in 10.72 ...........need to know much more optimisations that u would have probably used...

==(Lakshman)=> My algorithm is not only depends upon optimization tweaks but also have better complexity.
Some suggestion:1.Use unsigned prime array.(Segmented sieve is much faster)2.Reduce mod operation.3.fast IO.


Last edit: 2015-09-02 05:56:12
2015-08-30 13:09:38 Priyanshu Srivastava
15016491 - Please check this solution. I think it is giving correct answers for all cases.
2015-08-30 00:14:06 Tejasv Gupta
@admin Please tell me whether my approach is correct or not moreover where else can I optimize it
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.