该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$\hspace{15pt}$这道题是C题的共轭题目！

$\hspace{15pt}$给你一个长度为 $N$ 的排列 $P = (P_1, P_2, \dots ,P_N)$ ，该排列由 $(1, 2, 3, \dots, N)$ 组成.

$\hspace{15pt}$对于一个长度为 $N$ 排列 $Q$ 来说，定义 $Q$ 的姊妹排列 $\bar{Q}$ 是执行下面操作刚好一次之后能产生的新排列中 字典序 最小的排列.

• 选择一个二元组 $(l, r)$ 满足 $1\leq l \leq r \leq N$ ，然后翻转 $(Q_l, Q_{l + 1}, \dots ,Q_{r-1},Q_{r})$, 换句话说，把排列 $Q = (Q_1, Q_2, \dots ,Q_N)$ 替换成 $\bar{Q} = (Q_1,\dots, Q_{l-1},Q_r, Q_{r-1}, \dots , Q_{l+1}, Q_{l},Q_{r+1}, \dots,Q_N)$

$\hspace{15pt}$求使得其姊妹排列 $\bar{Q}$ 刚好是 $P$ 的排列 $Q$ 的数量，答案对 $998244353$ 取模。

$\hspace{15pt}$形式化的说，求使下面这个式子成立的排列 $Q$ 的数量：

• $\bar{Q} = P$

$\hspace{15pt}$给你 $T$ 组样例，请你分别求解每一个.

Constraints

• $1 \leq T$
• $1 \leq N \leq 5 \times 10^5$
• $P$ 是 $(1, 2, \dots, N)$ 的排列
• $N$ 的和不超过 $5 \times 10^5$
• 所有输入均为整数

Input

通过标准输入输入数据，满足以下格式：

$T \\ case_1 \\ case_2\\ .\\ .\\ case_T\\$

每一组测试用例满足以下格式：

$N \\ P_1 \ P_2 \ P_3 \ \dots \ P_N$

Output

输出共 $T$ 行，对于第 $i$ 行，你要输出第 $i$ 组测试用例的答案.

对于每一个测试用例，你要输出 $1$ 个数字，表示答案，对 $998244353$ 取模.

Samples

4
3
1 3 2
1
1
4
4 3 2 1
6
1 2 6 5 4 3

2
1
0
9