You are given a grid $a$ of size $n \times m$. The rows are numbered from $1$ to $n$ from top to bottom, and the columns are numbered from $1$ to $m$ from left to right. Each cell of the grid is either blocked or free. Cells $(1, 1)$ and $(n, m)$ are free.

A set $S$ of cells of $a$, which may include blocked cells, is called good if the following conditions hold:

• $S$ is non-empty;
• for every cell $(i, j)$ belonging to $S$, every path from $(1, 1)$ to $(n, m)$ that passes only through free cells, moves one cell down or one cell right at each step, and passes through $(i, j)$ also passes through all other cells of $S$.

Count the number of good sets of cells of $a$ 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^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^6$).

The $i$-th of the following $n$ lines contains a string $a_{i, 1} a_{i, 2} \ldots a_{i, m}$ ($a_{i, j} \in \{0, 1\}$) — the $i$-th row of the grid. If $a_{i, j} = 1$, then cell $(i, j)$ is free; otherwise, it is blocked. It is guaranteed that $a_{1, 1} = a_{n, m} = 1$.

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 a single integer — the answer to the problem modulo $998\,244\,353$.

Note

In the first example, the only non-empty set of cells is $\{(1, 1)\}$, and it is good. Therefore, the answer is $1$.

In the third example, there is no path from $(1, 1)$ to $(2, 2)$ that passes only through free cells. Therefore, every non-empty set of cells is good, so the answer is $2^4 - 1 = 15$.

In the fifth example, the set $\{(2, 2), (3, 2)\}$ is good because every path from $(1, 1)$ to $(4, 4)$ that passes only through free cells and passes through either of these cells also passes through the other. On the other hand, the set $\{(3, 3), (4, 3)\}$ is not good: the path $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$ passes through $(3, 3)$ but does not pass through $(4, 3)$. It can be shown that the total number of good sets is $162$.