题目背景

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

米尔嘉瞪我。

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

题目描述

给定一个数 $n$，求满足 $\varphi(x)\mid n$ 的正整数 $x$ 的个数。

其中 $a\mid b$ 表示 $a$ 整除 $b$，$\varphi(x)$ 表示欧拉函数。

输入格式

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

由于输入已经给出 $n$ 的标准质因数分解，因此无需自行对 $n$ 做 Pollard-Rho 分解。

对于每组询问：

• 首先输入一个整数 $s$；
• 接下来 $s$ 行，每行两个整数 $p_i,\alpha_i$，表示 $n=\prod_{i=1}^{s}p_i^{\alpha_i}$；
• 保证 $p_i$ 为质数，且 $p_i<p_{i+1}$。

特别地，当 $n=1$ 时，其标准质因数分解为空，此时输入 $s=0$，后面没有质因子行。

输出格式

对于每组数据输出一行一个整数，表示满足条件的 $x$ 的个数，对 $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$。

对于 $n=8$，共有 $14$ 个解：

$\varphi(15)=\varphi(16)=\varphi(20)=\varphi(24)=\varphi(30)=8$；

$\varphi(5)=\varphi(8)=\varphi(10)=\varphi(12)=4$；

$\varphi(3)=\varphi(4)=\varphi(6)=2$；

$\varphi(1)=\varphi(2)=1$。

这些值均整除 $8$。

数据范围

对于 $100\%$ 的数据，$T=5$，$1\le n\le10^{18}$。

本整理版约定：当 $n=1$ 时使用 $s=0$ 表示空质因数分解；当 $n>1$ 时 $s\ge1$。

时空限制

• 时间限制：$2000\text{ ms}$
• 空间限制：$512\text{ MiB}$