For a permutation$^{\text{∗}}$ $q$ of size $m \ge 3$, define $f(q)$ to be a sequence $b$ of size $m - 2$ such that $b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2})$ for all $1 \le i \le m - 2$. Here, $\operatorname{med}(x, y, z)$ denotes the second smallest element among $\{x, y, z\}$.

You are given an array $a$ of size $n$, where some elements may be $0$. It is guaranteed that $a$ contains the values $1$ and $n$ (that is, there exist indices $i, j$ such that $a_i = 1$ and $a_j = n$).

Find the number of permutations $p$ of size $n$ satisfying the following conditions:

• $p$ is consistent with $a$: for all $1 \le i \le n$, if $a_i \neq 0$, then $p_i = a_i$.
• All elements of $f(p)$ are distinct.

Since the answer can be large, print 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 a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$).

It is guaranteed that all non-zero elements of $a$ are pairwise distinct. It is also guaranteed that $a$ contains the values $1$ and $n$.

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

Output

For each test case, print a single integer — the number of permutations $p$ satisfying the conditions, modulo $998\,244\,353$.

Note

In the first example, the only permutation consistent with the input is $p = [1, 3, 2]$. We have $f(p) = [2]$, since $\operatorname{med}(1, 3, 2) = 2$. The elements of $f(p)$ are distinct, so this permutation is valid. The answer is $1$.

In the second example, there are two permutations consistent with the input: $p = [3, 5, 4, 1, 2]$ and $p = [2, 5, 4, 1, 3]$.

• For $p = [3, 5, 4, 1, 2]$, $f(p) = [4, 4, 2]$.
• For $p = [2, 5, 4, 1, 3]$, $f(p) = [4, 4, 3]$.

In both cases, the value $4$ appears twice in $f(p)$. Thus, there are no valid permutations, and the answer is $0$.