I. Increasing Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a table $$$n \times m$$$, which we want to fill with integers. We denote the number in the cell at the intersection of $$$i$$$-th row and $$$j$$$-th column as $$$a_{i, j}$$$.

We want the following conditions to hold:

  • $$$1 \le a_{i, j} \le n + m$$$ for all $$$1 \le i \le n$$$, $$$1 \le j \le m$$$.

  • $$$a_{i-1, j} \lt a_{i, j}$$$ for all $$$1 \le i \le n-1$$$, $$$1 \le j \le m$$$.

  • $$$a_{i, j-1} \lt a_{i, j}$$$ for all $$$1 \le i \le n$$$, $$$1 \le j \le m-1$$$.

In other words, we want to fill the table with numbers from $$$1$$$ to $$$n+m$$$, so that the numbers in each row and column are increasing.

Also, we know the values of numbers in some cells of the table. Find the number of ways to choose the values of the numbers that we do not know, so that all the conditions above are satisfied. Since this number can be very large, print it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n, m$$$ $$$(1 \le n, m \le 2\cdot 10^5, 1 \le n\cdot m \le 2\cdot 10^5)$$$  — the size of the table. Then there are $$$n$$$ rows.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ $$$(1 \le a_{i, j} \le n+m$$$ or $$$a_{i, j} = -1)$$$. If $$$a_{i, j} \neq -1$$$, then the number at the intersection of the $$$i$$$-th row and $$$j$$$-th column is known (and equal to $$$a_{i, j}$$$); otherwise, it must be found.

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

Output

For each test case, print a single integer  — the number of ways to fill in the unknown values of the table so that all conditions are satisfied.

Example
Input
4
2 3
1 2 -1
-1 4 5
4 4
-1 -1 -1 -1
-1 -1 -1 -1
-1 4 4 -1
-1 -1 -1 -1
4 4
-1 -1 -1 -1
-1 -1 -1 -1
-1 4 5 -1
-1 -1 -1 -1
3 5
1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
Output
4
0
17
55
Note

In the first test case, we only need to choose the values of $$$a_{2, 1}$$$ and $$$a_{1, 3}$$$. $$$a_{2, 1}$$$ can take the values $$$2, 3$$$, and $$$a_{1, 3}$$$  — $$$3, 4$$$. There are $$$4$$$ options in total.

In the second test case, there is no such table because the condition $$$a_{3, 2} \lt a_{3, 3}$$$ is already violated.