Given two integers n and p, where p is a prime number, find the value of n! modulo p.

Input :
A single integer t, the number of test cases. Next t lines contain two space separated integers, n and p.
Output :
Output n! modulo p on each line.
Constraints :
1<=t<=1000 1<p<=10^9 1<=n<=10^9 Abs(n-p) <= 1000