Problem Description

Given the value of a positive integer $n$, compute the value of the following expression:

$$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j}$$

Since the result may be very large, you only need to output the value modulo $p$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

For each test case:

One line contains two positive integers $n, p$.

Output Format

For each test case, output one line with a positive integer, representing the required value.

2
2 1000000007
3 998244353

19
752

2
4 998244353
123456 1000000007

66420
3252328

Hint

This problem enables O2 optimization and bundled tests.

To eliminate incorrect solutions, the Constraints are intentionally set larger. Please pay attention to the impact of constant factors on your program.

Sample Explanation

Sample #1

For the first test case: $\operatorname{ans} = \gcd(1, 1)^2 + \gcd(1, 2)^3 + \gcd(2, 1)^3 + \gcd(2, 2)^4 = 1^2 + 1^3 + 1^3 + 2^4 = 3 + 16 = 19$. Therefore, the answer is $19 \bmod (10^9 + 7) = 19$.

Constraints

Subtask	$\sum n$	Score	Time Limit
$1$	$1 \leq \sum n \leq 500$	$10 \operatorname{pts}$	$1.00 \operatorname{s}$
$2$	$1 \leq \sum n \leq 5 \times 10^5$	$40 \operatorname{pts}$	$3.20 \operatorname{s}$
$3$	No special constraints	$50 \operatorname{pts}$	$6.00 \operatorname{s}$

For $100\%$ of the testdata, $1 \leq \sum n \leq 1.5 \times 10^6$, $2 \leq p \leq 2^{31} - 1$ and $p$ is prime, $1 \leq T \leq 2$.

Translated by ChatGPT 5