题目描述

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

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

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

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

输入格式

本题共 $T$ 组数据，第一行一个正整数 $T$（$1\le T \le 10^4$）。

之后对于每组数据，第一行一个正整数 $n$（$1\le n \le 26$）。

之后 $n$ 行，每行给出字符 $c_i$ 和一个正整数 $h_{c_i}$ ，表示集合 $S$ 中有 $h_{c_i}$ 个字符 $c_i$。

数据保证 $1\le \sum_{i=1}^n h_{c_i} \le 10^7$

输出格式

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

输入样例

1
2
a 2
b 1

输出样例

665496236

提示

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