Problem Description

小马给出了一个可重小写字符集合 $S$。

Alice 初始时有空串 $A$，Bob 初始时有空串 $B$。

两人轮流等概率取出集合 $S$ 中的一个字符 $c$，将它拼接到自己的字符串的后面，直至 $S$ 为空，每个字符只能被取一次，Alice 先手。

如果最终 $A$ 的字典序严格大于 $B$，则 Alice 胜利，求其获胜的概率，答案对 $998244353$​ 取模。

Input

本题共 $T$ 组数据，第一行一个正整数 $T$。

之后对于每组数据，第一行一个正整数 $n$。

之后 $n$ 行，每行给出字符 $c_i$ 和一个正整数 $h_{c_i}$，表示集合 $S$ 中有 $h_{c_i}$ 个字符 $c_i$。（$1 \leq T \leq 10^4,1 \leq n \leq 26,1 \leq \sum_{i=1}^n h_{c_i }\leq 10^7$）

Output

对于每组数据，输出一行，包含一个整数，表示答案。

1
2
a 2
b 1

665496236

Hint

$A=ba,B=a$ 或 $A=ab,B=a$ 满足条件，两种情况概率均为 $\frac{1}{3}$，获胜概率为 $\frac{2}{3}$。