Boring Factorials

Input

The first line contains the number of queries t~(1 \le t \le 1000).

Each of the following $t$ lines contains two integers n~(1 \le n \le 2 \cdot 10^9) and p~(1 < p \le 2 \cdot 10^9), where $p$ is a prime number. It is known that |n - p| \le 1000.

Output

For each query, output the value of n! \bmod p on a separate line.

Examples