Kujou Karen is a lazy girl. Because she is lazy, she bought a cleaning robot.

Kujou Karen's house can be modeled as an $n \times m$ grid, with coordinates from $(1,1)$ to $(n,m)$. Every evening, Karen starts the cleaning robot at $(1,1)$. After starting, the robot moves along a pre-set path and stops when it returns to $(1,1)$.

Due to some technical reasons, the cleaning robot can only move right (column index plus one) or down (row index plus one). To ensure the robot can successfully return to $(1,1)$, Karen installed some passages in her house such that:

• If the robot is currently at $(i, m)$, moving right one step will take it to $(i, 1)$.
• If the robot is currently at $(n, j)$, moving down one step will take it to $(1, j)$.

Karen hopes that after starting the robot, it will pass through every cell exactly once before returning to $(1,1)$. This way, the house can be cleaned thoroughly without taking too much time. After a simple calculation, Karen quickly obtained all different plans (two plans are different if and only if the order in which they pass through the cells is different). Karen then input all these plans into the cleaning robot.

One day, Karen bought some new furniture. After placing the furniture, there were some obstacles in the house that the cleaning robot could not pass through. Consequently, for all the previously prepared plans, the cleaning robot will hit an obstacle and stop working.

For a plan $S$, define $f(S)$ as the number of cells the cleaning robot passed through before hitting an obstacle in this plan. Now, Karen wants to calculate the sum of $f(S)$ for all previously different plans.

Input

The input contains multiple test cases. The first line contains an integer $T$ representing the number of test cases.

For each test case, the first line contains two integers $n, m$, representing the size of Karen's house.

The next $n$ lines each contain a binary string of length $m$. The $j$-th character of the $i$-th line is $0$ if the cell at $(i, j)$ is not an obstacle, and $1$ otherwise.

It is guaranteed that $(1,1)$ is not an obstacle and there is at least one obstacle.

Output

For each test case, output a single integer representing the answer, modulo $998,244,353$.

Examples

Input 1

2
2 4
0111
1111
2 4
0010
1000

Output 1

2
5

Note

When $n = 2, m = 4$, there are two valid plans:

In the first plan, the robot passed through 4 cells before hitting the obstacle at $(1,3)$. In the second plan, the robot passed through 1 cell before hitting the obstacle at $(2,1)$. Therefore, the answer for the second test case is $1 + 4 = 5$.

Constraints

• Test case 1 (20%): $n \le 4, m \le 4$.
• Test case 2 (30%): $n \le 50, m \le 50$, and all cells except $(1,1)$ are obstacles.
• Test case 3 (50%): $n \le 50, m \le 50$.
• For all test cases, $T \le 10$.