You are given an integer $n$ and an array $a$ of length $n-1$.

For a permutation$^{\text{∗}}$ $p$ of length $n$, define

$$ v_i=\min\left(\max_{1\le j\le i}p_j, \max_{i+1\le j\le n}p_j\right), $$

where $1\le i\le n-1$.

In other words, cut the permutation between positions $i$ and $i+1$, take the maximum element on each side, and let $v_i$ be the smaller of these two values.

Your task is to count the number of permutations $p$ of length $n$ such that $v_i=a_i$ for each $1\le i\le n-1$.

Output the answer 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 one integer $n$ ($2\le n\le 10^6$) — the length of $p$.

The second line contains $n-1$ integers $a_1,a_2,\ldots,a_{n-1}$ ($1\le a_i\le n$) — the elements of $a$.

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

Output

For each test case, output one integer — the number of suitable permutations, modulo $998\,244\,353$.

Note

In the first test case, both permutations $[1,2]$ and $[2,1]$ satisfy $v_1=1$.

In the second test case, the only suitable permutations are $[2,1,3]$ and $[3,1,2]$.

In the third test case, no suitable permutation exists.