BORING2  Boring Factorials (Extended)
Factorial is one of the most attractive word this week, it is proposed to reload a famous problem. Is it so boring ?
As the reload edition wasn't hard enough, we'll extend constraints.
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 (not so) close to P, and asks them to find N! modulo P. He asks T such queries.
Input
The first line of input contains an integer
T, the number of test cases.
On each of the next T lines, your are given
two integers N, and P a prime number.
Output
For each test case, you have to print N! modulo P.
Example
Input: 3 2 5 5 11 21 71
Output: 2 10 6
Constraints
0 < T < 10^3 0 < N < 10^100 1 < P < 10^100, a prime number Abs(NP) < 10^6
Problem designed to be solvable using some 'slow' languages like Python (333B of code) in the third of the time_limit.
Warning : To get AC here, you need to get around 1000 points (approx) in challenge edition.
My best python code get AC under 5s. (edit 20170211, after compiler changes)
;) Have fun.
hide comments
mehmetin:
20140728 08:31:16
 Last edit: 20140728 09:21:37 

[Lakshman]:
20140311 08:20:20
Really very happy Finally Accepted.


Francky:
20140306 10:47:29
Congratulations to Min_25 as the first solver in the way the problem was designed for.

Added by:  Francky 
Date:  20140304 
Time limit:  15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  DCEPC11B 