题目描述

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$.

4
2 2
.#
##
2 3
...
...
3 4
#.#.
.#.#
#.#.
6 5
###..
###..
##.##
##.##
..###
..###

6
1
0
210