For a permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$, the corresponding coloring sequence $$$s$$$ can be obtained by the following coloring process:

Initially, there are $$$n$$$ white cells indexed from $$$1$$$ to $$$n$$$ from left to right. At second $$$0$$$, the score of each cell is $$$0$$$.
At second $$$i$$$ ($$$1 \le i \le n$$$),
- If $$$i \gt 1$$$, find the nearest black cell to the cell $$$p_i$$$, and increase the score of that cell by $$$1$$$. In case there are multiple nearest black cells, choose the cell with the lowest index. Cell $$$y$$$ is called the nearest black cell to cell $$$x$$$ only if cell $$$y$$$ is black and there is no black cell $$$z$$$ satisfying $$$|x-z| \lt |x-y|$$$.
- Color the cell $$$p_i$$$ black.

After all cells are colored black, denoting $$$s_i$$$ as the score of cell $$$i$$$ ($$$1 \le i \le n$$$), we get the coloring sequence $$$s$$$.

You might want to read the notes for a better understanding.

You are given an incomplete coloring sequence $$$s$$$, where some $$$s_i$$$ are already fixed, while others are not yet determined. Count how many different permutations $$$p$$$ can produce this coloring sequence. Since the answer may be large, you need to output 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.

For each test case, the first line contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$).

The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$-1 \leq s_i \leq n-1$$$). Here, $$$s_i=-1$$$ means $$$s_i$$$ has not been determined. And $$$s_i \neq -1$$$ means $$$s_i$$$ has already been fixed.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, output the total of different permutations $$$p_1, p_2, \ldots, p_n$$$ that can produce the coloring sequence, modulo $$$998\,244\,353$$$.

Note

In the first test case, $$$p=[3,1,2]$$$ and $$$p=[3,2,1]$$$ can produce the coloring sequence $$$s=[-1,-1,1]$$$.

For $$$p=[3,1,2]$$$, the coloring process is shown as the following picture.

$\text{[math]}$

$\text{[math]}$

$\text{[math]}$

$\text{[math]}$

The grid at seconds $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ respectively when $$$p=[3,1,2]$$$.

For $$$p=[3,2,1]$$$, the coloring process is shown as the following picture.

$\text{[math]}$

$\text{[math]}$

$\text{[math]}$

$\text{[math]}$

The grid at seconds $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ respectively when $$$p=[3,2,1]$$$.

Permutation Blackhole

Examples