AT_awtf2026algo_e Even Rows

$ N $ 行 $ M $ 列の盤面があります． 上から $ i $ 行目，左から $ j $ 列目のマスをマス $ (i,j) $ と呼ぶことにします． 各マスは空であるか，駒が $ 1 $ つ置かれているかのいずれかの状態です． 盤面の状態は $ N $ 個の長さ $ M $ の文字列 $ S_1,S_2,\ldots,S_N $ で与えられ， $ S_{i} $ の $ j $ 番目の文字が `.` ならばマス $ (i,j) $ は空で，`O` ならばマス $ (i,j) $ には駒が置かれています． 整数 $ L,R $ ( $ 1 \leq L \leq R \leq N $ ) に対し， $ f(L,R) $ を以下のように定義します． - 盤面の $ L $ 行目から $ R $ 行目だけを取り出し， $ R-L+1 $ 行からなる盤面を得る．この新しい盤面を $ X $ と呼ぶことにする． - あなたは $ X $ に対して以下の操作を $ 0 $ 回以上繰り返すことができる． - 駒を $ 1 $ つ選び，それを四近傍のうち好きなマスに移動させる． ただし，移動先のマスに別の駒があってはいけない． また，駒が $ X $ の外に出るような操作もできない． - あなたの目標は， $ X $ のすべての行についてその行にある駒の個数が偶数である状態にすることである． 目標を達成することが不可能なら $ f(L,R)=0 $ とする． 可能なら，そのために必要な最小の操作回数を $ f(L,R) $ とする． $ \sum_{1 \leq L \leq R \leq N} f(L,R) $ を $ 998244353 $ で割った余りを求めてください． $ 1 $ つの入力につき， $ T $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ M $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

各テストケースについて，答えを出力せよ．

### Sample Explanation 1 最初のテストケースにおける $ f(L,R) $ の値は以下の通りです． - $ f(1,1)=0 $ - $ f(1,2)=2 $ - $ f(1,3)=0 $ - $ f(2,2)=0 $ - $ f(2,3)=1 $ - $ f(3,3)=0 $ ### Constraints - $ 1 \leq T \leq 250000 $ - $ 2 \leq N \leq 500000 $ - $ 2 \leq M \leq 10 $ - $ S_i $ は `.`, `O` からなる長さ $ M $ の文字列である - $ T $ ケースにわたる $ N $ の総和は $ 500000 $ 以下