DCEPC11B  Boring Factorials
Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend has been helping them out. But as it goes, Sameer and Arpit have got bored of problems involving factorials. Reason being, the factorials are too easy to calculate in problems as they only require the residue modulo some prime and that is easy to calculate in linear time. So to make things interesting for them, Aman  The Mathemagician, gives them an interesting task. He gives them a prime number P and an integer N close to P, and asks them to find N! modulo P. He asks T such queries.
Input
First line contains an integer T, the number of queries asked.
Next T lines contains T queries of the form “N P”. (quotes for clarity)
Output
Output exactly T lines, containing N! modulo P.
Example
Input: 3 2 5 5 11 21 71 Output: 2 10 6Constraints:
1 <= T <= 1000
1 < P <= 2*10^9
1 <= N <= 2*10^9
Abs(NP) <= 1000hide comments
dheeraj2806:
20180813 09:01:06
Try to apply Wilson's theorem. 

anirudnits:
20171110 20:13:15
can anyone verify the test case 1999554444 1999555444.Thank you 

anurag44:
20170414 17:05:24
Learned Fermat's Little theorem and Wilson's Theorem.


anonymous:
20170410 00:18:04
@sanjay5797: this testcase is invalid because 5183 is not a prime 

sanjay5797:
20170214 13:26:48
be careful for the testcase


Sarthak Munshi:
20160909 18:29:51
Study Wilson's theorem and Fermat's Little Theorem . Write them side by side and find a link . DONE . 

asifjishan:
20160901 19:49:42
having time limit problem. 

more_practice:
20160628 22:14:22
not so tough if you just have studied wilson 

faceless_man:
20160628 12:54:29
Wilson's Theorem !! AC in two go 

Murad Al Wajed:
20160424 18:09:42
awesome problem. learned something new 
Added by:  dce coders 
Date:  20131001 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PASGPC PASFPC PYTHON PYTHON3 PY_NBC 
Resource:  Own Problem 