P12470 [Math×Girl] 互质与整除

>“还可以连接一个东西。”米尔嘉说，“$1$ 的原始 $n$ 次方根的个数是欧拉老师 $\varphi$ 函数的值。函数 $\varphi(n)$ 在 $1\le k米尔嘉瞪我。 “互质？”米尔嘉看着窗外说，“我们来做道有趣的题吧！”

给定一个数 $n$，求出满足以下方程的 $x$ 的个数。 $$\varphi(x)\mid n$$ 其中 $\mid$ 为整除符号，$a\mid b$ 表示 $a$ 整除 $b$。 $\varphi(x)$ 为欧拉 $\varphi$ 函数，详见题目背景。

本题有多组数据，第一行输入一个整数 $T$，表示数据组数。 _米尔嘉已经帮你实现了 Pollard-Rho 算法，_ 所以输入给出的是 $n$ 的标准质因子分解形式 $n=\prod_{i=1}^s p_i^{\alpha_i}$。 对于每一组询问，我们首先给出一个整数 $s$。 后面 $s$ 行每行两个整数表示 $p_i,\alpha_i$，保证 $p_i

对于每组数据，一行输出一个数表示解的个数。 _为了节约你的时间，米尔嘉已经封装好了 modint 以进行中国剩余定理合并答案。_ 所以输出对 $998244353$ 取模后的结果即可。

### 样例解释 质因数分解前 $n$ 分别为： $8,2024,1145141919810$ 第一个例子中的 $14$ 个解是： $\varphi(15)=\varphi(16)=\varphi(20)=\varphi(24)=\varphi(30)=8\mid 8$ $\varphi(5)=\varphi(8)=\varphi(10)=\varphi(12)=4\mid 8$ $\varphi(3)=\varphi(4)=\varphi(6)=2\mid 8$ $\varphi(1)=\varphi(2)=1\mid 8$ ### 数据范围 | 子任务 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $0$ | $10$ | $n\in[1,10^7]$ | | $1$ | $10$ | $n\in[1,10^9]$ | | $2$ | $20$ | $n\in[1,10^{12}]$ | | $3$ | $20$ | $n\in[1,10^{14}]$ | | $4$ | $20$ | $n\in[1,10^{16}]$ | | $5$ | $20$ | - | 对于 $100\%$ 数据，保证 $T=5$，$n\in[1,10^{18}],s\ge 1$。