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.

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.

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