Problem Statement

You are given an integer $N$ and a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.

For a permutation $Q=(Q_1,Q_2,\ldots,Q_N)$ of $(1,2,\ldots,N)$, let $Q'=(Q_1',Q_2',\ldots,Q_N')$ be the lexicographically smallest permutation obtainable by performing the following operation exactly once:

• Choose a pair of integers $(l,r)$ satisfying $1\le l\le r\le N$, and reverse $Q_l,Q_{l+1},\ldots,Q_r$. More precisely, replace $Q$ with $(Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N)$.

Find the number, modulo $998244353$, of permutations $Q$ of $(1,2,\ldots,N)$ such that $Q'=P$.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T$
• $1\le N\le 5\times 10^5$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• The sum of $N$ over all test cases is at most $5\times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
P_1 P_2 \ldots P_N

Output

Output the answers for the test cases in order, separated by newlines.