E. Non-Similar Paths
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After years of research, you (Nick Belov) finally find your favorite biking place. You want to explore as many different bike paths as possible. However, you don't see a difference in exploring two bike paths that are very similar. You want to know how many bike paths you can explore such that each path is non-similar to any of your previously explored paths.

You are given an $$$n \times m$$$ grid. Each cell is either passable or impassable.

A valid path starts at the top-left cell $$$(1,1)$$$ and ends at the bottom-right cell $$$(n,m)$$$. At each step, you may move either right or down, and every cell visited by the path must be passable.

Represent each valid path by a string containing $$$m-1$$$ characters 'R' and $$$n-1$$$ characters 'D', denoting moves right and down, respectively.

Two valid paths $$$a$$$ and $$$b$$$ are called similar if there exists a sequence of valid paths $$$a=q_1,q_2,\ldots,q_{|q|}=b$$$ such that, for every $$$1 \le j \lt |q|$$$, the paths $$$q_j$$$ and $$$q_{j+1}$$$ differ in exactly 2 adjacent positions.

Let $$$S$$$ be a set of valid paths such that no two distinct paths in $$$S$$$ are similar.

Find the maximum possible size of $$$S$$$. Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n,m \le 10^6, 2 \le n \cdot m \le 10^6)$$$ — the number of rows and columns of the grid.

Each of the next $$$n$$$ lines contains a string of length $$$m$$$ describing one row of the grid.

A '.' denotes a passable cell, and a '#' denotes an impassable cell.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer — the maximum possible size of $$$S$$$, modulo $$$998\,244\,353$$$.

Example
Input
4
5 5
.....
.....
..#..
.....
.....
2 2
#.
..
3 2
.#
..
#.
1 10
..........
Output
2
0
1
1
Note

In the first test case (same as second picture), here is a possible set $$$S$$$:

$$$\{\texttt{RRRRDDDD},\texttt{DDDDRRRR}\}$$$

In the second test case, the starting cell is impassable so there are no valid paths.

In the third and fourth test cases there is only $$$1$$$ valid path.