背景

:::epigraph 朝复夕，朝夕复。 :::

题目描述

本题和试题 G 朝复习没有关系。

小 T 准备出一些经典的问题……

对于给定一个长度为 $n$ 的排列 $p = \{p_1, p_2, \dots, p_n\}$，小 T 将进行一次操作 $(i, j)$：

• 取一对下标 $1 \le i < j \le n$，交换 $p$ 中的 $p_i$ 和 $p_j$。

对于所有不同的合法操作 $(i, j)$，小 T 需要计算交换之后的排列所表示的置换的阶数之和。

由于答案可能很大，小 T 需要计算答案对 $998\,244\,353$ 取模的值。

请帮助小 T 计算这个问题。

试题的提示中附带有有关于置换和排列的相关信息。

输入格式

第一行输入一个整数 $T \ (1 \le T \le 10^5)$，表示测试数据的数量。

每组测试数据第一行输入一个整数 $n \ (2 \le n \le 10^5)$，表示排列的长度。

随后一行输入 $n$ 个整数 $p_1, p_2, \dots, p_n \ (1 \le p_i \le n)$，表示所给定的排列。

保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$，且每组测试数据给定序列一定是一个合法的排列。

输出格式

对于每组测试数据输出一行一个整数，表示对于所有不同的合法操作 $(i, j)$，交换之后的排列所表示的置换的阶数之和对 $998\,244\,353$ 取模的值。

2
3
2 3 1
4
2 1 4 3

6
20

提示

样例 1 解释

对于第 $1$ 组测试数据，共有 $3$ 种不同的交换方式：

• 交换 $p_1$ 和 $p_2$，排列变为 $p = \{3, 2, 1\}$，可以注意到 $p^2 = \mathrm{id}_3$，因为 $p(p(1)) = p(3) = 1$，$p(p(2)) = p(2) = 2$，$p(p(3)) = p(1) = 3$，因此阶数为 $2$。
• 交换 $p_1$ 和 $p_3$，排列变为 $p = \{1, 3, 2\}$，可以注意到 $p^2 = \mathrm{id}_3$，阶数为 $2$。
• 交换 $p_2$ 和 $p_3$，排列变为 $p = \{2, 1, 3\}$，可以注意到 $p^2 = \mathrm{id}_3$，阶数为 $2$。

因此答案为 $6$。

提示

一个 $1$ 到 $n$ 的排列是一个长度为 $n$ 且其中每个 $1$ 到 $n$ 的整数都出现且仅出现一次的序列，这个排列的长度也为 $n$.

令 $S = \{1, 2, \dots, n\}$，一个 $1$ 到 $n$ 的置换是指从 $S$ 到 $S$ 的一个双射。

一个长度为 $n$ 的排列 $p = \{p_1, p_2, \dots, p_n\}$ 可以表示一个置换 $p$，也即 $p(i) = p_i$.

例如第 $1$ 组样例的 $p = \{2, 3, 1\}$ 表示的置换是 $p(n): \{1, 2, 3\} \to \{1, 2, 3\}$，其中

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

长度为 $n$ 恒等置换 $\mathrm{id}_n: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ 定义为 $\mathrm{id}_n(i) = i$，例如一个长度为 $4$ 的恒等置换 $\mathrm{id}_4$ 有：

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

两个置换 $p$ 和 $q$ 的复合 $p \circ q$ 表示的是 $p \circ q(i) = p(q(i))$ 这个置换。

长度为 $n$ 的置换的幂次 $p^m$（其中 $m$ 是非负整数）定义为

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

长度为 $n$ 的置换的阶数 $\mathrm{ord}(p)$ 定义为最小的正整数 $k$，满足 $p^k = \mathrm{id}_n$.