$3 \times n$ のグリッドが与えられる。ある染色方案が合法であるとは、以下の条件をすべて満たすことをいう。

• 各列において、ちょうど1つのマスが染色されている。
• 隣接する2列において、染色されているマスの行番号が異なる。

各マス $(i, j)$ にはパラメータ $s_{i, j}$ が設定されている。

• $s_{i, j} = \texttt{0}$ の場合、そのマスは染色してはならない。
• $s_{i, j} = \texttt{1}$ の場合、そのマスは必ず染色しなければならない。
• $s_{i, j} = \texttt{?}$ の場合、そのマスは染色しても染色しなくてもよい。

すべての合法な染色方案について、染色されていないマスの連結成分の最大面積を求め、その総和を計算せよ。答えは非常に大きくなる可能性があるため、$998,244,353$ で割った余りを求めよ。

入力

本問は複数のテストケースを含む。

入力の最初の行には、2つの非負整数 $c, t$ が含まれる。それぞれテストケースの番号とテストケースの数である。$c=0$ はそのテストケースがサンプルであることを示す。

続いて各テストケースが順に入力される。各テストケースの形式は以下の通りである。

• 1行目に2つの正整数 $n, p$ が与えられる。
• 続く3行には、長さ $n$ の文字列 $s_{i, 1}, \dots, s_{i, n}$ がそれぞれ与えられる。

出力

各テストケースについて：

• すべての合法な染色方案における、染色されていないマスの連結成分の最大面積の総和を $998,244,353$ で割った余りを1行に出力せよ。

入出力例

入力 1

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

出力 1

5
6
20

注記

このサンプルには3つのテストケースが含まれる。

• 1つ目のテストケースについて：
  • $(1, 1)$ が染色される場合、染色されていないマスの連結成分の最大面積は $2$ である。
  • $(2, 1)$ が染色される場合、染色されていないマスの連結成分の最大面積は $1$ である。
  • $(3, 1)$ が染色される場合、染色されていないマスの連結成分の最大面積は $2$ である。
  • すべての方案の総和は $(2 + 1 + 2) \bmod 998,244,353 = 5$ となる。
• 2つ目のテストケースについて：
  • $(1, 1)$ が染色される場合、染色されていないマスの連結成分の最大面積は $3$ である。
  • $(3, 1)$ が染色される場合、染色されていないマスの連結成分の最大面積は $3$ である。
  • 注意：$(2, 1)$ が染色される場合は合法な方案ではない。なぜなら、合法な染色方案は隣接する列で染色されるマスの行番号が異なっていなければならないからである。
  • すべての方案の総和は $(3 + 3) \bmod 998,244,353 = 6$ となる。

制約

すべてのテストケースにおいて、以下が成り立つ。

• $1 \le t \le 5$
• $1 \le n \le 300$
• すべての $1 \le i \le 3$ および $1 \le j \le n$ に対して、$s_{i, j} \in \{\texttt{0}, \texttt{1}, \texttt{?}\}$

• 特殊性質 A：すべての $1 \le i \le 3$ および $1 \le j \le n$ に対して、$s_{i, j} \ne \texttt{?}$ である。
• 特殊性質 B：すべての $1 \le i \le n$ に対して、$s_{1, i} = \texttt{0}$ である。
• 特殊性質 C：すべての $1 \le i \le 3$ および $1 \le j \le n$ に対して、$(i+j) \bmod 2 = 0$ ならば $s_{i, j} = 0$ である。