题目描述

给定正整数 $n$ 的值，求出下面这个式子的值：

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

由于结果可能很大，所以你只需要求出结果对 $p$ 取模的值。

输入格式

本题有多组测试数据。

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

一行，两个正整数 $n, p$。

输出格式

对于每组数据，输出一行，一个正整数，表示所求的值。

2
2 1000000007
3 998244353

19
752

2
4 998244353
123456 1000000007

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$。