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
2015-03-27 14:29:56 vabs
A very nice mathematical problem
2015-03-05 22:59:31 Abhinandan Agarwal
It is a very good problem, I enjoyed doing it :) ..
2015-03-01 14:17:21 [Lakshman]
Please delete Abhinandan Agarwal comment. I don't understand what people get by putting these kind of comment.
@Abhinandan Agarwal
If it is really obvious try this http://www.spoj.com/problems/BORING

Last edit: 2015-03-01 14:25:57
2015-03-01 13:52:15 Abhinandan Agarwal
^loved the problem

Last edit: 2015-03-06 07:56:56
2015-02-14 06:02:29 Manoj Pandey
Try to reduce number of times mod is done. Finally AC !!
2015-02-12 12:04:29 Yash
Very nice question, learnt two great theorems; but the time limit is too strict..same code AC in C++, TLE Java :(
2015-02-07 05:41:06 vikrant
how to calculate n! mod p when p is non-prime??any suggestions?
2015-01-19 19:28:42 /* Nitin Jaiman */
Lovely problem.
2015-01-01 21:04:45 sHaShAnK sHeKhAr
Very strict time limit...
2014-12-30 13:13:12 Anubhav Balodhi
good problem on number theory ^_^
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.