BORING  Boring Factorials (Reloaded)
Factorial is one of the most attractive word this week, it is proposed to reload a famous problem. Is it so boring ?
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^4 0 < N < 4×10^18 1 < P < 4×10^18, a prime number Abs(NP) < 10^4
Problem designed to be solvable using some 'slow' languages like Python (333B of code).
It is highly recommended to solve in a very fast way the original problem! Basic solution, even in fast language should give TLE.
Time limit is set as sqrt(correct × basic). The "basic" code gave me 0.00s to the original problem with slow IO.
If you don't find this reload edition hard enough, please consider the challenge edition with more serious constraints.
;) Have fun.
hide comments
teequila_:
20210131 20:11:26
Also here, runs very fast in my local testcases, but exceeds time limit for the submission. Any tips? Is the usage of BigInteger in java too inefficient for this problem?


fanxin:
20210129 16:14:38
@Francky Can you tell me why the result is "runtime error (NZEC)". I've tried different input, they can all give right answers.


jacobian_det:
20200513 19:33:31
@Francky: How to avoid overflow issue giving WA in CPP?


Avik Sarkar:
20180603 15:13:05
HI. I used Willson's theorem + Inverse Modulo . Can anyone suggest me a hint of any faster way. Here is my submission: ************** edited ********* ( Please edit if it violates rules. But please give a hint. )


free mind ;):
20150926 09:16:29
@Francky sir can you tell why i am getting runtime error , i am new in python, is this because range function or something else and can you please tell why my c++ solution giving WA . :) 

vishu:
20150813 03:00:17
@Francky sir,can you please tell me for what test cases it is giving wrong answer.Is it a specific input or it is giving wrong answer due to overflow? submission id14880828


Curiosa:
20150318 18:13:33
@Francky, could you please check my solution? Is the idea behind my solution "basic" (in your terms)? My solution is still slow compared to others, is this because of Java?


ivar.raknahs:
20141104 16:14:49
@francky=> can u tell me where my code fails (id:12812179) and can i get AC with this kind of approach?. Thanks


Tarun Garg:
20140727 19:03:12
@Francky where my code is falling out..?


[Lakshman]:
20140309 15:09:59
@Francky Finally Accepted with C++ but with worst running time.

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