Shrooks

Limits: 2 sec., 512 MiB

Shrek wants to place \(n\) rooks on a \(n\times n\) board, so that the following conditions hold:

• There is exactly \(1\) rook in each row and each column;

• Manhattan distance between any two rooks doesn’t exceed \(n\).

To make things worse, Donkey already placed some rooks (fortunately, each row and each column still contains at most one rook). Find the number of ways to place the remaining rooks so that conditions hold. Since it can be large, output it modulo \(998244353\).

Here, the Manhattan distance between the rook in the cell on the intersection of row \(x_1\) and column \(y_1\) and the rook in the cell on the intersection of row \(x_2\) and column \(y_2\) is defined as \(|x_1 - x_2| + |y_1-y_2|\).

Input

Each test consists of multiple test cases. The first line contains a single integer \(t\) — number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer \(n\) — size of the board.

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\). If \(a_i = -1\), it means row \(i\) doesn’t yet have a rook. Otherwise, it indicates that there is a rook at the intersection of row \(i\) and column \(a_i\).

Output

For each test case, output a single integer, the answer modulo \(998244353\).

Constraints

\(1 \leq t\leq 10^5\),

\(2 \leq n\leq 2\cdot 10^5\),

the sum of \(n\) over all test cases doesn’t exceed \(2\cdot 10^5\),

\(a_i = -1\) or \(1 \leq a_i \leq n\) for all \(1\leq i \leq n\),

if \(a_i, a_j\neq -1\) for \(i\neq j\), then \(a_i\neq a_j\).

Samples

Input (stdin) сopy	Output (stdout) сopy
6 2 1 2 3 -1 -1 -1 4 1 -1 -1 -1 5 1 -1 -1 -1 5 6 3 -1 -1 -1 -1 4 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1	1 4 1 0 6 92

Notes

In the first test case, the rooks are already placed, and they satisfy the conditions:

♖
	♖

 

In the second test case, there are \(4\) ways to place rooks:

♖
		♖
	♖

   

		♖
♖
	♖

   

	♖
♖
		♖

   

	♖
		♖
♖

 

In the third test case, there is exactly one such way:

♖
			♖
		♖
	♖

 

In the fourth test case, there are two rooks placed so far:

♖
				♖

The manhattan distance between them is already \(8>5\), so there is no satisfying placement of remaining rooks.