假设你有一个长度为 $M$ 的数组 $B$。你的目标是使 $B$ 成为一个回文。

如果对于每个 $1 \le i \le M$，都有 $B_i = B_{M+1-i}$，则称长度为 $M$ 的数组 $B$ 是一个回文。

为了实现这一目标，你将选择一个 $\{1, 2, \dots, M\}$ 的排列 $P$，并使用它执行以下过程：

在第 $i$ 步（$1 \le i \le M$）中，你必须选择恰好一个下标 $j$（$1 \le j \le M$）并将 $B_j$ 设为 $P_i$。

允许在不同的步骤中选择相同的下标 $j$。

当 $P$ 的所有 $M$ 个元素都被处理完毕，或者在 $B$ 首次成为回文后，该过程立即结束。

定义 $f(B, P)$ 为：如果你最优地选择每次操作的下标，使 $B$ 成为回文所需的最少步数。

特别地：

• 如果 $B$ 初始时已经是回文，则 $f(B, P) = 0$。
• 如果即使在处理完 $P$ 的每个元素后也无法使 $B$ 成为回文，我们定义 $f(B, P) = M + 1$。

给你一个长度为 $N$ 的数组 $A$。

计算对于 $\{1, 2, \dots, N\}$ 的所有可能排列 $P$，$f(A, P)$ 的总和。

由于答案可能很大，请将结果对 $998\,244\,353$ 取模后输出。

输入格式

输入按以下格式给出：

T
N
A_1 A_2 ... A_N
...

数据范围

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 5000$
• $1 \le A_i \le N$
• 保证所有测试用例中 $N^2$ 的总和不超过 $5000^2$。

输出格式

对于每个测试用例，输出一个整数，表示对于 $\{1, 2, \dots, N\}$ 的所有排列 $P$：

$$\sum_{P} f(A, P)$$

的值对 $998\,244\,353$ 取模后的结果。

样例

输入样例 1

4
3
1 2 3
4
2 3 3 2
6
4 6 4 6 4 6
10
1 5 2 10 2 6 3 1 10 2

输出样例 1

8
0
5040
31363200

说明

• 测试用例 1：对于 $P = [1, 2, 3]$ 且 $A = [1, 2, 3]$，所需的最少操作步数为 1，因为 $A$ 可以在第一步操作后变成回文。
• 测试用例 2：由于 $A$ 初始时已经是回文，因此对于任何排列 $P$，都有 $f(A, P) = 0$。