P16400 [ECUSTPC 2026 Spring] Morning Again, Evening Again

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

**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.

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.

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$.

### 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