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$$$.

Median Permutation

Examples