你正在管理一个由 $N$ 个人组成的团队，编号为 $1$ 到 $N$。在团队中，每个人都认为其他人比自己更强或更弱。为了发放年终奖，你需要以某种方式对团队进行排名。一个排名 $P$ 是 $1$ 到 $N$ 的一个排列，其中 $P_1$ 是排名最高的人，而 $P_N$ 是排名最低的人。排名完成后，团队中的每个人都能看到结果。

每个人的不快乐得分等于在排名中比他高、但被他认为更弱的人数。如果我们计算每个人的不快乐得分，并将其中最大或最差的 $K$ 个不快乐得分相加，就得到了该排名的得分。例如，如果一个排名的不快乐得分按升序排列为 $[0, 1, 2, 2, 3]$，那么对于 $K = 2$，得分为 $5 (3+2)$；对于 $K = 3$，得分为 $7 (3+2+2)$。

给定 $N$、$K$ 以及每个人对其他人强弱的看法，求随机选择一个排名时，其不快乐得分的期望值。答案可以表示为 $\frac{P}{Q}$，其中 $Q \neq 0$，请输出 $(P \cdot Q^{-1})$ 对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T (1 \le T \le 50)$，表示测试用例的数量。对于每个测试用例，第一行包含两个整数 $N$ 和 $K (1 \le K \le N \le 16)$。接下来的 $N$ 行，每行包含 $N$ 个大写字符。第 $i$ 行的第 $j$ 个字符表示第 $i$ 个人对第 $j$ 个人的看法。如果字符为 'S'，则表示 $i$ 认为 $j$ 更强。如果字符为 'W'，则表示 $i$ 认为 $j$ 更弱。如果 $i = j$，则字符为 'X'。保证 $N > 12$ 的测试用例数量最多为 $3$ 个。

输出格式

对于每个测试用例，输出一行，表示随机选择一个排名时，其不快乐得分的期望值，结果对 $998244353$ 取模。

样例

输入格式 1

3
3 2
XSW
SXW
WSX
4 3
XSWS
WXSW
SSXS
SWWX
1 1
X

输出格式 1

499122178
499122179
0