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