H. Morrow by Morrow
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem has no relation with Problem G CS:Go Over.

Little T is preparing some classic problems $$$\ldots$$$

Given a permutation $$$p = \{p_1, p_2, \ldots, p_n\}$$$ of length $$$n$$$, Little T will perform exactly one operation $$$(i, j)$$$:

  • Choose a pair of indices $$$1 \le i \lt j \le n$$$, and swap $$$p_i$$$ and $$$p_j$$$ in $$$p$$$.

For all different valid operations $$$(i, j)$$$, Little T needs to calculate the sum of the orders of the permutations represented by the permutation after the swap.

Since the answer can be very large, Little T needs to calculate the answer modulo $$$998\,244\,353$$$.

Please help Little T calculate this problem.

The hints section of the problem provides related information about permutations.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$), representing the length of the permutation.

The next line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$1 \le p_i \le n$$$), representing the given permutation.

It is guaranteed that $$$\sum n \le 3 \times 10^5$$$ over all test cases, and the input in each test case is guaranteed to be a valid permutation.

Output

For each test case, output a single line with an integer representing the sum of the orders of the permutations represented by the permutation after the swap for all different valid operations $$$(i, j)$$$, modulo $$$998\,244\,353$$$.

Example
Input
2
3
2 3 1
4
2 1 4 3
Output
6
20
Note

For the 1st test case, there are $$$3$$$ different ways to swap:

  • Swap $$$p_1$$$ and $$$p_2$$$, the permutation becomes $$$\{3, 2, 1\}$$$. Note that $$$p^2 = \text{id}$$$, because $$$p(p(1)) = p(3) = 1$$$, $$$p(p(2)) = p(2) = 2$$$, $$$p(p(3)) = p(1) = 3$$$, so the order is $$$2$$$.
  • Swap $$$p_1$$$ and $$$p_3$$$, the permutation becomes $$$\{1, 3, 2\}$$$. Note that $$$p^2 = \text{id}$$$, so the order is $$$2$$$.
  • Swap $$$p_2$$$ and $$$p_3$$$, the permutation becomes $$$\{2, 1, 3\}$$$. Note that $$$p^2 = \text{id}$$$, so the order is $$$2$$$.

Therefore, the answer is $$$6$$$.

Additional notes

A permutation sequence of $$$1$$$ to $$$n$$$ is a sequence of length $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ appears exactly once. The length of this permutation sequence is also $$$n$$$.

Let $$$S = \{1, 2, \ldots, n\}$$$. A permutation mapping from $$$1$$$ to $$$n$$$ refers to a bijection from $$$S$$$ to $$$S$$$.

A permutation sequence $$$p = \{p_1, p_2, \ldots, p_n \}$$$ of length $$$n$$$ can represent a permutation mapping $$$p(n)$$$, that is, $$$p(i) = p_i$$$.

For example, $$$p = \{2, 3, 1\}$$$ in the 1st test case represents the permutation mapping $$$p(n): \{1, 2, 3\} \rightarrow \{1, 2, 3\}$$$, where $$$$$$ p(1) = 2, p(2) = 3, p(3) = 1. $$$$$$

The identity permutation of length $$$n$$$, $$$\text{id}_n: \{1, 2, \ldots, n\} \rightarrow \{1, 2, \ldots, n\}$$$, is defined as $$$\text{id}_n(i) = i$$$. For example, an identity permutation of length 4, $$$\text{id}_4$$$, has: $$$$$$ \text{id}_4(1) = 1, \text{id}_4(2) = 2, \text{id}_4(3) = 3, \text{id}_4(4) = 4. $$$$$$

The composition $$$p \circ q$$$ of two permutations $$$p$$$ and $$$q$$$ represents the permutation where $$$p \circ q(i) = p(q(i))$$$.

The power $$$p^m$$$ (where $$$m$$$ is a non-negative integer) of a permutation of length $$$n$$$ is defined as $$$$$$ p^m = \begin{cases} p \circ p^{m - 1}, &m \ge 1;\\ \text{id}_n, & m = 0. \end{cases} $$$$$$

The order $$$\text{ord}(p)$$$ of a permutation of length $$$n$$$ is defined as the smallest positive integer $$$k$$$ such that $$$p^{k} = \text{id}_n$$$.