P5282 [Template] Fast Factorial Algorithm.

One day, NaCly_Fish happened to see an efficient algorithm for computing factorial modulo a large prime, but she was too inexperienced to code it. So she generated testdata by brute force, and asks you to help write the std. What, you ask why it is not guaranteed that the modulus can be used for NTT? If it were, people might pass by precomputing a table, or the answer might overflow int. Anyway, you are a genius, so you can surely solve this problem instantly.

You are given a positive integer $n$ and a prime $p$. You need to compute: $$ n! \text{ mod } p$$ There are $T$ test cases.

The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain two positive integers $n, p$, with the meaning described above.

Output $T$ lines, each being the answer for one test case.

### Constraints: For $10\%$ of the testdata: $p = 998244353$. For another $10\%$ of the testdata: $p = 1004535809$. For $100\%$ of the testdata: $1 \le n < p \le 2^{31}-1$, $1 \le T \le 5$. It is guaranteed that $p$ is prime. [Hint] Please make sure your algorithm runs in no more than $\Theta(\sqrt n \log n)$ time complexity. The time limit is more than ten times that of the std. Translated by ChatGPT 5