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
6

Constraints

1 ≤ T ≤ 1000

1 < P ≤ 2×109

1 ≤ N ≤ 2×109

Abs(N-P) ≤ 1000

Added by:dce coders
Date:2013-10-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC
Resource:Own Problem

hide comments
2019-05-24 14:27:30
@anirudnits 502781432 answer from my AC
In case of n!%p==0 answer is p not 0
2019-04-22 18:59:09
When I submitted this problem on vjudge it got accepted. But my runtime was 1790 ms whilst time limit being 1000 ms. When I submitted on the main site, I got TLE. What's wrong with vjudge?
2018-08-13 09:01:06
Try to apply Wilson's theorem.
2017-11-10 20:13:15
can anyone verify the test case 1999554444 1999555444.Thank you
2017-04-14 17:05:24
Learned Fermat's Little theorem and Wilson's Theorem.
2017-04-10 00:18:04 anonymous
@sanjay5797: this testcase is invalid because 5183 is not a prime
2017-02-14 13:26:48
be careful for the testcase
70 5183
in toolkit it gives answer as 0 but accepted when i got answer as5183
2016-09-09 18:29:51 Sarthak Munshi
Study Wilson's theorem and Fermat's Little Theorem . Write them side by side and find a link . DONE .
2016-06-28 22:14:22
not so tough if you just have studied wilson
2016-06-28 12:54:29
Wilson's Theorem !! AC in two go
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.