You are given a $3 \times n$ grid. A coloring scheme is defined as valid if and only if:

• Exactly one cell is colored in each column.
• The colored cells in adjacent columns are in different rows.

Each cell $(i, j)$ has a parameter $s_{i, j}$:

• If $s_{i, j} = \texttt{0}$, the cell must not be colored.
• If $s_{i, j} = \texttt{1}$, the cell must be colored.
• If $s_{i, j} = \texttt{?}$, the cell may be colored or not colored.

You need to calculate the sum of the sizes of the largest connected components of non-colored cells across all valid coloring schemes. Since the answer may be large, output the result modulo $998,244,353$.

Input

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c=0$ indicates that the test case is a sample.

For each test case:

• The first line contains two positive integers $n$ and $p$.
• The next three lines each contain a string of length $n$, representing $s_{1, 1}, \dots, s_{1, n}$, $s_{2, 1}, \dots, s_{2, n}$, and $s_{3, 1}, \dots, s_{3, n}$ respectively.

Output

For each test case:

• Output a single line containing a non-negative integer, representing the sum of the sizes of the largest connected components of non-colored cells across all valid coloring schemes, modulo $998,244,353$.

Examples

Input 1

0 3
1
?
?
?
2
?0
?1
?0
2
??
??
??

Output 1

5
6
20

Note 1

This sample contains $3$ test cases.

• For the first test case:
  • If $(1, 1)$ is colored, the size of the largest connected component of non-colored cells is $2$.
  • If $(2, 1)$ is colored, the size of the largest connected component of non-colored cells is $1$.
  • If $(3, 1)$ is colored, the size of the largest connected component of non-colored cells is $2$.
  • The sum of all schemes is $(2 + 1 + 2) \bmod 998,244,353 = 5$.
• For the second test case:
  • If $(1, 1)$ is colored, the size of the largest connected component of non-colored cells is $3$.
  • If $(3, 1)$ is colored, the size of the largest connected component of non-colored cells is $3$.
  • Note that the case where $(2, 1)$ is colored is not a valid scheme, because a valid coloring scheme requires that colored cells in adjacent columns are in different rows.
  • The sum of all schemes is $(3 + 3) \bmod 998,244,353 = 6$.

Constraints

For all test cases:

• $1 \le t \le 5$;
• $1 \le n \le 300$;
• For all $1 \le i \le 3$ and $1 \le j \le n$, $s_{i, j} \in \{\texttt{0}, \texttt{1}, \texttt{?}\}$.

• Special Property A: For all $1 \le i \le 3$ and $1 \le j \le n$, it is guaranteed that $s_{i, j} \ne \texttt{?}$.
• Special Property B: For all $1 \le i \le n$, it is guaranteed that $s_{1, i} = \texttt{0}$.
• Special Property C: For all $1 \le i \le 3$ and $1 \le j \le n$, if $(i+j) \bmod 2 = 0$, then $s_{i, j} = 0$.