Let $[A_1, A_2, \ldots, A_n]$ be an array of $n$ positive integers. Define array $f(A)$ as followed:

For each integer $i$ from $1$ to $n$:

• If there exists integer $j$ such that $j \lt i$ and $A_j \lt A_i$, $f(A)_i=\max\limits_{j \lt i,A_j \lt A_i} j$. That is, $f(A)_i$ is the index of the rightmost element before $i$ whose value is strictly smaller than $A_i$.
• Otherwise $f(A)_i=0$.

We call the array $[P_1,P_2,\ldots,P_n]$ of non-negative integers a cute array if there exists an array $A$ such that $f(A)=P$.

Given a length $n$ array $X$ in which $-1\le X_i\le n$ holds for all $i$ from $1$ to $n$. Count the numbers of cute arrays $X'$ formed by replacing the $-1$s in $X$ with integers from $0$ to $n$. As the number can be very large, print it modulo $998\,244\,353$.

Input

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

The first line of each test cases contain an integer $n$ ($1\le n\le5000$) denoting the length of $X$.

The second line contain $n$ integers $X_1,X_2,\ldots,X_n$ ($-1\le X_i\le n$).

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

Output

For each test cases, output a single integer denoting the number of arrays $X'$ such that $X'$ is a cute array, modulo $998\,244\,353$.

Note

For the first test case, only $[0,0,0]$ and $[0,0,2]$ are cute arrays among all possible $X'$. $[0,0,0]$ is a good cute array because $f([1,1,1])=[0,0,0]$, and $[0,0,2]$ is a good array because $f([1,1,2])=[0,0,2]$.

For the second test case, only $[0,1,1,0]$, $[0,1,1,1]$ and $[0,1,1,3]$ are cute arrays among all possible $X'$.