#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/18/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Successor Swap - Repovive Standard Round 6 | Repovive

18D. Successor Swap

2000 pts2s256 MB

You are given a permutation $p$ of the integers from $1$ to $n$ .

In one operation, you may do the following:

choose an index $i$ such that $i < p_i$ ;
set $j = p_i$ ;
swap the elements at indices $i$ and $j$ . In other words, swap $p_i$ and $p_j$ .

Find the number of distinct permutations that can be reached after performing any number of operations, possibly zero.

Print the answer modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$p$ is a permutation of the integers from $1$ to $n$

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

4
1 2 3 4

Case 2

4
2 3 4 1

Case 3

4
4 3 1 2

Explanation

Case 1

No operation can be performed, so the only reachable permutation is $(1,2,3,4)$ .

Case 2

Starting from $(2,3,4,1)$ , the following sequences of chosen indices produce all reachable permutations:

no operations: $(2,3,4,1)$
$1$ : $(3,2,4,1)$
$2$ : $(2,4,3,1)$
$3$ : $(2,3,1,4)$
$1,1$ : $(4,2,3,1)$
$1,3$ : $(3,2,1,4)$
$2,2$ : $(2,1,3,4)$
$1,1,1$ : $(1,2,3,4)$

Therefore, the answer is $8$ .

Case 3

Starting from $(4,3,1,2)$ , choosing the indices

none,
$1$ ,
$2$ ,
$1,1$ ,
$1,2$ ,
$1,1,1$

produces the six distinct reachable permutations. Therefore, the answer is $6$ .

Output

Case 1

Case 2

Case 3

Input

Case 1

8
2 3 1 5 4 8 6 7

Case 2

10
10 9 8 6 7 1 4 2 5 3

Explanation

Case 1

For example, choosing the indices $1,1,4,6,6$ produces $(1,2,3,4,5,6,7,8)$ . Considering all legal sequences gives $24$ distinct reachable permutations.

Case 2

For example, applying the operation at index $1$ nine times produces $(1,2,3,4,5,6,7,8,9,10)$ . Considering all legal sequences gives $98$ distinct reachable permutations.

Output

Case 1

Case 2

You are given a permutation $p$ of the integers from $1$ to $n$ .

In one operation, you may do the following:

choose an index $i$ such that $i < p_i$ ;
set $j = p_i$ ;
swap the elements at indices $i$ and $j$ . In other words, swap $p_i$ and $p_j$ .

Find the number of distinct permutations that can be reached after performing any number of operations, possibly zero.

Print the answer modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$p$ is a permutation of the integers from $1$ to $n$

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

No operation can be performed, so the only reachable permutation is $(1,2,3,4)$ .

Starting from $(2,3,4,1)$ , the following sequences of chosen indices produce all reachable permutations:

no operations: $(2,3,4,1)$
$1$ : $(3,2,4,1)$
$2$ : $(2,4,3,1)$
$3$ : $(2,3,1,4)$
$1,1$ : $(4,2,3,1)$
$1,3$ : $(3,2,1,4)$
$2,2$ : $(2,1,3,4)$
$1,1,1$ : $(1,2,3,4)$

Therefore, the answer is $8$ .

Starting from $(4,3,1,2)$ , choosing the indices

none,
$1$ ,
$2$ ,
$1,1$ ,
$1,2$ ,
$1,1,1$

produces the six distinct reachable permutations. Therefore, the answer is $6$ .

For example, choosing the indices $1,1,4,6,6$ produces $(1,2,3,4,5,6,7,8)$ . Considering all legal sequences gives $24$ distinct reachable permutations.

For example, applying the operation at index $1$ nine times produces $(1,2,3,4,5,6,7,8,9,10)$ . Considering all legal sequences gives $98$ distinct reachable permutations.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

18D. Successor Swap

Constraints

Input

Output

Samples

18D. Successor Swap

Constraints

Input

Output

Samples