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.

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 $

For each test case, output the answer.

### Sample Explanation 1 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 $ .