Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has $n$ $01$ strings $s_i$, and he wants to know the number of $01$ antisymmetric strings of length $2L$ which contain all given strings $s_i$ as continuous substrings.

A $01$ string $s$ is antisymmetric if and only if $s[i] \neq s[|s|-i+1]$ for all $i \in [1,|s|]$.

It is too difficult for Rikka. Can you help her?

In the second sample, the strings which satisfy all the restrictions are $000111,001011,011001,100110$.

Input

The first line contains a number $t(1 \leq t \leq 5)$, the number of the testcases.

For each testcase, the first line contains two numbers $n,L(1 \leq n \leq 6, 1 \leq L \leq 100)$.

Then $n$ lines follow, each line contains a $01$ string $s_i(1 \leq |s_i| \leq 20)$.

Output

For each testcase, print a single line with a single number -- the answer modulo 998244353.

2
2 2
011
001
2 3
011
001

1
4