問題文

$2$ 以上の整数 $n$ と長さ $n$ の整数列 $A=(A_1,A_2,\ldots,A_n)$ が与えられます。ここで、全ての $i=1,2,\ldots,n$ について $A_i=-1$ または $1\leq A_i\leq n$ が成り立ちます。

$(1,2,\ldots,n)$ の順列 $P=(P_1,P_2,\ldots,P_n)$ のうち、以下の条件を全て満たすものの個数を $998244353$ で割った余りを求めてください。

• 全ての $1$ 以上 $n$ 以下の整数 $i$ について、$A_i\neq -1$ ならば $P_i=A_i$ である
• 全ての $1$ 以上 $n-2$ 以下の整数 $i$ について、$\min(P_i,P_{i+1})\leq \min(P_{i+1},P_{i+2})$ である

1 つのファイルにつき $T$ 個のテストケースが与えられるので、その全てに対して上記の問題を解いてください。

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$

ここで $\mathrm{testcase}_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。

$n$
$A_1$ $A_2$ $\cdots$ $A_n$

• 入力は全て整数で与えられる
• $1\leq T\leq 5000$
• $2\leq n\leq 5000$
• $A_i=-1$ または $1\leq A_i\leq n$
• $i\neq j$ なる $i,j$ に対して、$A_i\neq -1, A_j\neq-1$ ならば $A_i\neq A_j$
• $T$ 個のテストケースにわたる $n$ の総和は $5000$ 以下

出力

$T$ 行出力してください。$i\ (1\leq i\leq T)$ 行目には $i$ 番目のテストケースに対する答えを出力してください。$T$ 行目の出力の後も改行してください。

サンプル

4
3
-1 2 -1
5
3 -1 2 -1 -1
5
5 4 3 2 1
20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1
2
0
799043977