Background

:::epigraph Morning again, evening; morning and evening again. :::

Problem Description

This problem is not related to Problem G “Morning Review”.

Little T plans to prepare some classic problems……

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

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

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

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

Please help Little T solve this problem.

The hints of the problem include some information about permutations and arrangements.

Input Format

The first line contains an integer $T \ (1 \le T \le 10^5)$, indicating the number of testdata.

For each testdata, the first line contains an integer $n \ (2 \le n \le 10^5)$, indicating the length of the permutation.

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

It is guaranteed that $\sum n \le 3 \times 10^5$ over all testdata, and in each testdata the given sequence is a valid permutation.

Output Format

For each testdata, output one integer per line: for all different valid operations $(i, j)$, the sum of the orders of the permutations represented by the permutation after swapping, modulo $998\,244\,353$.

2
3
2 3 1
4
2 1 4 3

6
20

Hint

Explanation of Sample 1

For the $1$-st testdata, there are $3$ different ways to swap:

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

Therefore, the answer is $6$.

Hint

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

Let $S = \{1, 2, \dots, n\}$. A permutation (bijection) of $1$ to $n$ means a bijection from $S$ to $S$.

A permutation of length $n$, $p = \{p_1, p_2, \dots, p_n\}$, can represent a permutation (bijection) $p$, i.e., $p(i) = p_i$.

For example, in Sample 1, $p = \{2, 3, 1\}$ represents the permutation $p(n): \{1, 2, 3\} \to \{1, 2, 3\}$, where

$$p(1) = 2,\ p(2) = 3,\ p(3) = 1.$$

The identity permutation of length $n$, $\mathrm{id}_n: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$, is defined as $\mathrm{id}_n(i) = i$. For example, the identity permutation of length $4$, $\mathrm{id}_4$, has:

$$\mathrm{id}_4(1) = 1,\ \mathrm{id}_4(2) = 2,\ \mathrm{id}_4(3) = 3,\ \mathrm{id}_4(4) = 4.$$

The composition of two permutations $p$ and $q$, written as $p \circ q$, means the permutation $p \circ q(i) = p(q(i))$.

The power $p^m$ of a permutation of length $n$ (where $m$ is a non-negative integer) is defined as

$$p^m = \begin{cases} p \circ p^{m-1}, & m \ge 1; \\ \mathrm{id}_n, & m = 0. \end{cases}$$

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

Translated by ChatGPT 5