P15781 [JAG 2025 Summer Camp #3] Grid Painting

There is an $H \times W$ grid, where initially every cell is painted white. Let $C_{i,j}$ ($1 \leq i \leq H$, $1 \leq j \leq W$) denote the color of the cell in the $i$-th row from the top and the $j$-th column from the left. You can paint the grid by repeating the following two operations any number of times, in any order. **Operation 1:** This operation may be applied only if the rightmost column of the grid is entirely white. First, perform a cyclic right shift of the entire grid by one column (i.e., for all $1 \leq i \leq H$, $1 \leq j \leq W$, replace $C_{i, (j \mod W) + 1}$ with $C_{i, j}$ simultaneously). Then, choose $1 \leq l \leq r \leq H$ and paint $C_{l, 1}, C_{l+1, 1}, \ldots, C_{r, 1}$ black. **Operation 2:** This operation may be applied only if the bottom row of the grid is entirely white. First, perform a cyclic downward shift of the entire grid by one row (i.e., for all $1 \leq i \leq H$, $1 \leq j \leq W$, replace $C_{(i \mod H) + 1, j}$ with $C_{i, j}$ simultaneously). Then, choose $1 \leq l \leq r \leq W$ and paint $C_{1, l}, C_{1, l+1}, \ldots, C_{1, r}$ black. Given the final grid after performing some operations, determine the number of operation sequences that could result in it. Since the answer can be very large, output it modulo $998244353 = 119 \times 2^{23} + 1$. Two operation sequences are considered different if they have different lengths, or if at any step either the shift direction or the segment painted black differs. :::align{center}  :::

The input consists of multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 100$), representing the number of test cases. $T$ test cases follow. Each test case is given in the following format. $$ \begin{aligned} & H \ W \\ & S_1 \\ & \vdots \\ & S_H \end{aligned} $$ For each test case, the first line contains integers $H$ ($1 \leq H \leq 100$) and $W$ ($1 \leq W \leq 100$), representing the height and width of the grid, respectively. Each of the following $H$ lines contains a string $S_i$ of length $W$, representing the final grid, consisting only of the characters ‘#’ and ‘.’. If the $j$-th character of $S_i$ is ‘#’, then $C_{i,j}$ is black, and if it is ‘.’, then $C_{i,j}$ is white.

Output one line per test case: the number of possible operation sequences modulo $998244353$.