SPOJ Brasil

Find $N!$ modulo $P$.

Input

The first line contains $T$ ($1 \le T \le 100,000$), the number of test cases.

Each of the next $T$ lines contains two integers $N$ ($0 \le N \le 10^{11}$) and $P$ ($2 \le P \le 10^{11}$), where $P$ is a prime.

Output

For each $N$ and $P$, output $N!$ modulo $P$.

Constraints

For each input file, It is guaranteed that (the sum of $\sqrt{P}) \le 320000$.

Example

Input

3
1000 9907
1000000 9999907
10000000000 99999999907

Output

4494
3354924
40583077821

Note

• Probably, $O(P)$ solutions will not pass.
• Intended solutions have a complexity of about $O(\sqrt{P} \log{P})$
• My solution runs in 0.5 seconds for each input file.