Rikka 有 $n$ 个集合 $S_1, S_2, \dots, S_n$，其中包含小写英文字母。如果存在一个下标 $i$，使得以下所有条件成立：$p_1 \in S_i, p_2 \in S_{i+1}, \dots, p_m \in S_{i+m-1}$，则称长度为 $m$ 的模式串 $p_1p_2 \dots p_m$ 与这些集合匹配。

初始时，所有集合均为空。Rikka 准备了一些操作来填充这些集合。每个操作的形式为“将字符 $c$ 加入集合 $i$”。每一轮，Rikka 会以相等的概率随机选择一个操作并执行。同一个操作可以被多次选择和执行。

求直到模式串 $p_1p_2 \dots p_m$ 与集合匹配所需的期望轮数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 5$)。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le m \le n \le 30$)。

接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $t_i$，由小写英文字母组成。每个字母 $t_{i,j}$ 代表一个将该字母加入集合 $i$ 的操作。每个字符串均非空，且每个字母最多出现一次。

每个测试用例的最后一行包含模式串：一个由小写英文字母组成的字符串 $p_1p_2 \dots p_m$。

输出格式

对于每个测试用例，如果模式串永远无法与集合匹配，输出 $-1$。否则，输出整数 $(p \cdot q^{-1}) \pmod{998\,244\,353}$，其中 $\frac{p}{q}$ 为期望轮数。

样例

样例输入 1

1
1 1
ab
a

样例输出 1

2

样例输入 2

1
3 2
acb
cb
ab
cb

样例输出 2

915057330

说明

对于第一个样例测试用例，期望值为 $\frac{1}{2} \cdot 1 + \frac{1}{2^2} \cdot 2 + \dots = 2$。