AT_awtf2026algo_e.Even Rows

There is a board with $N$ rows and $M$ columns. Let us call the cell at the $i$-th row from the top and $j$-th column from the left cell $(i,j)$.

Each cell is empty or has one piece placed on it. The state of the board is given by $N$ length-$M$ strings $S_1,S_2,\ldots,S_N$: if the $j$-th character of $S_{i}$ is ., cell $(i,j)$ is empty, and if it is O, cell $(i,j)$ has a piece placed on it.

For integers $L$ and $R$ ($1 \leq L \leq R \leq N$), define $f(L,R)$ as follows.

• Extract only rows $L$ through $R$ of the board, obtaining a board with $R-L+1$ rows. Call this new board $X$.

• You can repeat the following operation on $X$ zero or more times.

  • Choose one piece and move it to any of the cells adjacent to it (up, down, left, or right). Here, the destination cell must not have another piece on it. Also, you cannot perform an operation that would move a piece outside of $X$.

• Your goal is to reach a state where, for every row of $X$, the number of pieces in that row is even. If it is impossible to achieve the goal, let $f(L,R)=0$. If it is possible, let $f(L,R)$ be the minimum number of operations required to do so.

Find $\sum_{1 \leq L \leq R \leq N} f(L,R)$, modulo $998244353$.

Solve $T$ cases for each input.

有一个 $N$ 行 $M$ 列的棋盘。我们将从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子记为 $(i,j)$。

每个格子要么为空，要么恰好放置一枚棋子。棋盘的状态由 $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$ 上执行以下操作零次或多次：

  • 任选一枚棋子，并将其移动到与其相邻的任意一个格子（上、下、左、右）。目标格子必须为空；且不允许将棋子移出 $X$ 的边界。

• 目标状态是：$X$ 的每一行中，棋子数量均为偶数。若无法达到该目标，则令 $f(L,R)=0$；否则，令 $f(L,R)$ 为达成目标所需的最少操作次数。

求 $\sum_{1 \leq L \leq R \leq N} f(L,R)$ 对 $998244353$ 取模的结果。

对每组输入，需解决 $T$ 个测试用例。

The input is given from Standard Input in the following format:

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输入从标准输入中给出，格式如下：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例的格式如下：

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

For each test case, output the answer.

对于每个测试用例，输出答案。

Sample 1 Explanation:
The values of $f(L,R)$ in the first test case are as follows.

• $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$ is a string of length $M$ consisting of . and O.
• The sum of $N$ over the $T$ cases is at most $500000$.

样例 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$

约束条件

• $1 \leq T \leq 250000$
• $2 \leq N \leq 500000$
• $2 \leq M \leq 10$
• $S_i$ 是一个长度为 $M$ 的字符串，仅由字符 . 和 O 组成。
• 所有 $T$ 个测试用例的 $N$ 值之和不超过 $500000$。