Neko and Inu

Neko and Inu are good friends.
Neko has a box of energy crystals $A$. Inu has a box of energy crystals $B$.
Both of $A$ and $B$ have $n$ crystals. Each crystal has a different energy. You can think that energy is a positive integer.
Unfortunately, $A$ and $B$ are mixed together when Neko and Inu are playing games. Each pair of crystals $u (u \in A)$ and $v (v \in B)$ can produce two new crystals which energies are $u + v$ and $|u - v|$. The old crystals will disappear in the end.
So there are $2 n ^ {2}$ crystals finally. Let the new box of energy crystals called $C$. Neko and Inu are surprised to find each crystal in $C$ is different and their energies are continuous odd number from $1$ to $4 n ^ {2} - 1$.
Now, Neko and Inu want to know how many different $A$ and $B$ can be mixed into $C$. Calculate the answer after mod $998244353$.

The first line contains only one integer $T ( T \leq 50)$, which indicates the number of test cases.
For each test case, the first line contains one integer $m$ ,indicating the number of distinct primes of $n$.($1 \leq m \leq 10^5$).
The next $m$ line, each line contains two integers $p_{i}, a_{i}$.
Where $p_{i}$ is a prime.$n = \prod p_{i} ^ {a_{i}}, a_{i} > 0, \sum a_{i} \leq 10^5, p_{i} \leq 10^9 + 9$.
There are at most $10$ test cases which satisfies $\sum a_{i} \geq 10^3$.

For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer after mod $998244353$.

2
1
2 1
2
2 2
5 2

Case #1: 6
Case #2: 6060

for the first case:
A = {1, 3}, B = {4, 12}
A = {4, 12}, B = {1, 3}
A = {3, 5}, B = {6, 10}
A = {6, 10}, B = {3, 5}
A = {2, 6}, B = {7, 9}
A = {7, 9}, B = {2, 6}

2018中国大学生程序设计竞赛 - 网络选拔赛