「EZEC-4」求和
题目描述
给定正整数 $n$ 的值，求出下面这个式子的值：
$$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j}$$
由于结果可能很大，所以你只需要求出结果对 $p$ 取模的值。
输入输出格式
输入格式
**本题有多组测试数据。**
第一行，一个整数 $T$，表示数据组数。
对于每组数据：
一行，两个正整数 $n, p$。
输出格式
对于每组数据，输出一行，一个正整数，表示所求的值。
输入输出样例
输入样例 #1
2
2 1000000007
3 998244353输出样例 #1
19
752输入样例 #2
2
4 998244353
123456 1000000007输出样例 #2
66420
3252328说明
**本题开启 O2 优化和捆绑测试。**
**为了卡掉错解开大了数据范围，请注意常数因子对程序产生的影响。**
### 样例解释
#### 样例 #1
对于第一组数据：$\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$。所以答案为 $19 \bmod (10^9 + 7) = 19$。
### 数据范围
| Subtask | $\sum n$ | 分值 | 时限 |
| :------: | :------: | :------: | :------: |
| $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$ | 无特殊限制 | $50 \operatorname{pts}$ | $6.00 \operatorname{s}$ |
对于 $100\%$ 的数据，$1 \leq \sum n \leq 1.5 \times 10^6$，$2 \leq p \leq 2^{31} - 1$ 且 $p$ 为质数，$1 \leq T \leq 2$。