背景

加强版链接。

这是一道数学题，可是 LMX 给 HQZ 出的。

题目描述

定义积性函数 $f(n)=(\mu \ast\operatorname{Id_2})(n)$。

给定 $n,k$，你需要求出

$$\sum_{i_1\mid n}\sum_{i_2\mid i_1}\cdots\sum_{i_k\mid i_{k-1}}f(i_k)i_1i_k\mu^2\left(\dfrac{i_1}{i_k}\right)$$

Tips：

$\mu$ 表示莫比乌斯函数。

关于 $f$，$f(n)=\displaystyle \sum_{d\mid n}\mu(d)\left(\dfrac{n}{d}\right)^2$。

输入格式

本题有多组数据，第一行输入一个正整数 $T$，表示数据组数。

考虑到 $n$ 很大，所以我们会给出 $n$ 的标准质因子分解 $n=\displaystyle \prod_{i=1}^t p_i^{\alpha_i}$。

对于每一组询问，我们首先给出两个整数 $k,m$。

第二行给出 $t$，下面 $t$ 行每行两个整数表示 $p_i,\alpha_i$。

（保证 $p_i\ge p_{i-1},i\ge 2$，$\alpha_i\ge 1$）。

输出格式

对于每个询问，输出一行表示答案 $\mod m$ 的值。

5
3 998244353
3
3 2
5 1
7 1
4 1000000009
2
2 1
3 2
1 998244353
2
2 2
3 1
11451 191981012
11
2 1
3 1
5 1
7 1
11 1
13 1
17 1
19 1
23 1
29 1
31 1
514 520
2
2 10
3 10

189282114
124678
14965
82966193
260

提示

对于 $100\%$ 的数据，有 $T \le 20,n\le 10^{24},1\le k\le 10^6,m\le 1.14\times 10^9$。

测试点编号	$n$	$k$	$T$	特殊性质
$1$	$\le 80$	$\le 4$	$\le 5$	$N$
$2$	$\le 10^6$	$\le 10$
$3$	$\le 10^{12}$	$\le 20$	$\le 20$
$4$	$\le 10^{18}$	$\le 1$
$5$		$\le 10^3$
$6$		$\le 10^5$		$A$
$7$		$\le 10^6$		$B$
$8$	$\le 10^{24}$
$9$				$C$
$10\sim20$				$N$

性质 $A$：保证 $t\le 10$。

性质 $B$：保证 $n$ 的质因子分解 $\displaystyle\prod_{i=1}^t p_i^{\alpha_i}$ 中 $\alpha_i=1$。

性质 $C$：$m$ 是素数，且保证 $\gcd(n,m)=1$。