A path in a grid is called greedy if it starts at the top-left cell and moves only to the right or downward, always moving to its neighbor with the greater value (or either if the values are equal).

The value of a path is the sum of the values of the cells it visits, including the start and end.

Given a partially filled $$$2 \times n$$$ grid of integers between $$$1$$$ and $$$k$$$, count the number of ways to fill the empty cells such that in every subgrid$$$^{\text{∗}}$$$, there exists a greedy path that achieves the maximum value out of all down/right paths. Since the answer may be large, calculate it modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$ A subgrid of a $$$2 \times n$$$ grid $$$a_{i,j}$$$ is a grid formed from all cells $$$a_{x,y}$$$ such that $$$l_x \leq x \leq r_x$$$, $$$l_y \leq y \leq r_y$$$ for some $$$1 \leq l_x \leq r_x \leq 2$$$, $$$1 \leq l_y \leq r_y \leq n$$$.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 500$$$) — the number of columns and the range of integers in the grid, respectively.

Then two lines follow, the $$$i$$$-th line containing $$$n$$$ integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$-1 \leq a_{i,j} \leq k$$$, $$$a_{i,j} \neq 0$$$) — the values of cells in the $$$i$$$-th row of the grid, where $$$-1$$$ represents an empty cell.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, output a single integer — the number of ways to fill the grid that satisfy the above conditions, modulo $$$998\,244\,353$$$.

Note

In the first test case, the grids that satisfy the conditions are: $$$$$$ \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix}. $$$$$$

In the second test case, all ways to fill the grid satisfy the conditions.

Greedy Grid Counting

Examples