Factorial Modulo Prime

Given a positive integer n and a prime number p, your task is to compute the following:

\( n! \mod p \)

You need to process T test cases.

inputFormat

The first line contains an integer T denoting the number of test cases. Each of the following T lines contains two positive integers n and p (with p being a prime) separated by a space.

Note: If n is greater than or equal to p, then n! will be divisible by p and the answer is 0.

outputFormat

For each test case, output a single line containing the value of \( n! \mod p \).

sample

3
5 7
10 11
20 23

1
10
11