Notice

标程 TLE 了，因此时限变成 $2s$。

Description

给定长为 $n$ 的串 $s$ 和 $m$ 个串 $t_i$。

定义 $h(s, l, r) = \sum\limits_{i = 1}^m occur(s[l, r], t)\times w_i$，其中 $occur(s, t)$ 表示 $t$ 在 $s$ 中的出现次数。

求 $\sum\limits_{i = 1}^n\sum\limits_{j = i}^n h(s, i, j)^5\bmod 998244353$。

Input

第一行一个数 $T$，表示数据组数。

对于每组数据，第一行一个串 $s$。

第二行一个整数 $m$。

然后 $m$ 行，每行一个串 $t_i$ 和一个整数 $w_i$。

Output

$T$ 行每行一个非负整数，表示答案。

Sample Input #1

1
gongxinifaxianqiandaoti
3
ia 1
g 2
axia 3

Sample Output #1

1157160

Sample #2

Sample

Range

• $\text{subtask}1(10\ \text{pts})$：$n, m, |t_i|\le 50$。

• $\text{subtask}2(30\ \text{pts})$：$s, t_i$ 的每个字符在 ${a, b}$ 中随机生成，$w_i$ 在 $[0, 998244353)$ 中随机生成。

• $\text{subtask}3(30\ \text{pts})$：$T = 1$。

• $\text{subtask}4(30\ \text{pts})$：无特殊限制。

对于 $100\% $ 的数据，保证 $1\le T\le 5$，对于每组数据 $1\le n, \sum |t_i|, m\le 5\times 10^5, 0\le w_i < 998244353$，所以字符都是小写字母。