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:) .
hide comments
Michael Kharitonov:
20170207 21:46:03
Lakshman, I've beaten your time:) This problem is quite similar to DIVFACT3


Sifat Shishir:
20161026 23:09:04
Got AC :) Last edit: 20161027 17:48:04 

cena_coder:
20160713 08:08:14
now it is working up n<=10^6 and then TLE shit man :(


cena_coder:
20160706 06:54:56
i can't understand why it is showing WA Admin can u check it out for me id 17232977


varun bumb:
20160205 14:38:04
FINALLY, GREEN!!


varun bumb:
20151031 21:43:48
@[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 

Pranav Rai:
20150902 19:40:56
@admin I am getting a TLE  Can you suggest any improvements  http://www.spoj.com/submit/EASYFACT/id=14918201 

Arjav:
20150901 17:48:40
@Admin after too much struggle my solution get ac in 10.72 ...........need to know much more optimisations that u would have probably used...


Priyanshu Srivastava:
20150830 13:09:38
15016491  Please check this solution. I think it is giving correct answers for all cases. 

Tejasv Gupta:
20150830 00:14:06
@admin Please tell me whether my approach is correct or not moreover where else can I optimize it 
Added by:  [Lakshman] 
Date:  20150513 
Time limit:  5s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 