Background

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.

Problem Description

You are given a positive integer $n$ and a prime $p$. You need to compute:

There are $T$ test cases.

Input Format

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 Format

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

4
16777216 998244353
72267859 998244353
2333333 19260817
1919810 2147481811

789885751
569626621
16351109
1416439247

Hint

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