Zayin 喜欢在网上和女朋友聊天，并整理了一本情话词典。词典包含 $m$ 个词 $w_1, w_2, \dots, w_m$，每个词都有其对应的爱意值 $v_1, v_2, \dots, v_m$。 所有词均由小写英文字母组成。不在词典中的任何词，其爱意值为 0。

利用这本词典，Zayin 定义了一个字符串 $S$ 的“甜度”：

$$sweetness(S) = \frac{\sum_{l=1}^{|S|} \sum_{r=l}^{|S|} love(S(l, r))}{|S|}$$

其中 $S(l, r)$ 表示 $S$ 中从第 $l$ 个字符到第 $r$ 个字符（包含两端）的子串，$|S|$ 表示字符串 $S$ 的长度，$love(s)$ 表示如上定义的字符串 $s$ 的爱意值。 这意味着字符串 $S$ 的甜度等于其所有子串的爱意值之和除以 $S$ 的长度。

现在，Zayin 的女朋友给 Zayin 发来了一条由字符串 $S$ 组成的消息，并问了 Zayin 一个问题：$S$ 的所有子序列中，甜度的最大值是多少？子序列是指通过删除字符串 $S$ 中的部分或零个元素，且不改变剩余元素顺序而得到的字符串。

当 Zayin 和女朋友约会时，他的智商会从 301 降到 31。所以他请求你帮他解决这个问题。

输入格式

第一行包含一个整数 $T(T \le 80)$，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n(1 \le n \le 1000)$ 和 $m(1 \le m \le 1000)$，分别表示字符串 $S$ 的长度和词典的大小。第二行是一个字符串 $S$，随后有 $m$ 行，每行包含一个字符串 $w_i$ 和一个整数 $v_i$。 保证对于每个测试用例，$n, m < 1000$，$\sum |w_i| \le 4000$，$0 \le v_i \le 10^5$，且 $w_i$ 两两不同。 对于每个输入文件，$\sum n \le 3000$，$\sum m < 2000$，$\sum |w_i| \le 10000$。 所有字符串仅由小写英文字母组成。

输出格式

对于每个测试用例，你需要输出所有子序列中甜度的最大值。为了避免输出浮点数，你需要输出答案对 998244353 取模的结果。如果答案是 $\frac{A}{B}$，你需要输出 $A \times B^{-1} \pmod{998244353}$ 的值。

样例

输入 1

3
17 3
woyaoakccpcxiamen
ak 5
ccpc 6
xiamen 8
33 3
niweishenmezhengtianxunlianbuliwo
wo 3
se 1
zayin 7
39 2
programmingcontestandmewhichisimportant
me 11
gg 2

输出 1

499122179
499122178
499122182

说明

对于测试用例 1，甜度最大的子序列是 “ak”； 对于测试用例 2，甜度最大的子序列是 “wo”； 对于测试用例 3，甜度最大的子序列是 “me”。