题目背景

“还可以连接一个东西。”米尔嘉说，“$1$ 的原始 $n$ 次方根的个数是欧拉老师 $\varphi$ 函数的值。函数 $\varphi(n)$ 在 $1\le k<n$ 的范围内表示与 $n$ 互质的自然数的个数，也表示循环群的生成元的个数。”米尔嘉像是描绘 $\varphi$ 似地挥动手指，“最喜欢互质的尤里不在这里真可惜，今天你怎么没带她来？”
米尔嘉瞪我。

“互质？”米尔嘉看着窗外说，“我们来做道有趣的题吧！”

题目描述

给定一个数 $n$，求出满足以下方程的 $x$ 的个数。

其中 $\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<p_{i+1}$。

输出格式

对于每组数据，一行输出一个数表示解的个数。

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

3
1
2 3
3
2 3
11 1
23 1
6
2 1
3 2
5 1
7 1
101 2
178187 1

14
53
53

提示

样例解释

质因数分解前 $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$

数据范围

对于 $100\%$ 数据，保证 $T=5$，$n\in[1,10^{18}],s\ge 1$。