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.