F. Familiar?
time limit per test
5 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Note the unusual memory limit.

Consider the following pseudocode that processes a permutation $$$p$$$ of length $$$n$$$$$$^{\text{∗}}$$$:

function mystery(p):
    n = length of p
    st = an empty stack
    count = an array of length n filled with 0s
    for i from 1 to n:
        while st is not empty and p[i] < top of st:
            pop from st
            count[i] = count[i] + 1
        push p[i] into st
    return count

You are given an array $$$a$$$ of length $$$n$$$. Your task is to count the number of permutations $$$p$$$ of length $$$n$$$ such that, if $$$b$$$ is the array returned by mystery(p), the condition $$$a_i = b_i$$$ holds for all $$$i$$$ ($$$1 \le i \le n$$$) where $$$a_i \neq -1$$$.

Since the answer can be very large, output it modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 500$$$), representing the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-1 \le a_i \le n$$$), representing the elements in $$$a$$$.

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

Output

For each test case, output an integer representing the number of permutations, modulo $$$998\,244\,353$$$.

Example
Input
7
1
0
1
-1
1
1
4
0 0 -1 1
6
-1 -1 -1 -1 -1 -1
3
0 1 0
7
0 -1 0 -1 2 1 -1
Output
1
1
0
3
720
2
77
Note

In the first and second test cases, the only valid permutation is $$$[1]$$$.

In the fourth test case, the valid permutations are $$$[1,2,4,3]$$$, $$$[3,4,2,1]$$$, and $$$[1,4,3,2]$$$.

In the fifth test case, all permutations of length $$$6$$$ are valid.