题目描述

这是一个充满爱的社区！

社区中有 $n$ 名居民，每位居民 $i (1 \leq i \leq n)$ 在社区中都有一个他/她非常爱的居民 $a_i (1 \leq i \leq n)$。每两个居民爱着不同的居民。居民可以爱自己。保证 $n$ 是偶数。

有一天，发生了一件坏事：他们需要选择 $2$ 名居民，他们将永远被禁止结婚。

为了防止将来发生这样的事情，其余的 $n - 2$ 名居民会组成 $\frac{n}{2} - 1$ 组对象结婚，每组对象由 $2$ 个人组成（当然）。如果一组对象由居民 $x$ 和居民 $y$ 组成，而 $x$ 既不爱 $y$，$y$ 也不爱 $x$，那这也太怪了！因此这样的情况永远不会发生。

因此，作为婚姻规划者，您需要弄清楚如何安排这一切。您想知道不同婚姻计划的数量。两个婚姻计划是不同的，当且仅以下条件至少其一为真：

• 在一个计划中，某人 $i$ 已婚，而在另一个计划中，他/她未婚。
• 在一个计划中，某人 $i$ 与 $j$ 结婚，而在另一个计划中，他/她没有与 $j$ 结婚。

由于计划的数量可能非常多，请输出数量关于 $998244353$ 取模的结果。

输入格式

每组测试包含多个测试用例。第一行包含测试用例的数量 $T (1 \leq T \leq 10^4)$。

每个测试用例由两行组成。

第一行包含 $1$ 个整数 $n (4 \leq n \leq 5 \times 10^5)$，表示社区中的居民数量。保证 $n$ 是偶数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq n)$，其中 $a_i$ 表示居民 $i$ 爱的人。保证如果 $i \neq j (1 \leq i, j \leq n)$，则 $a_i \neq a_j$。

保证单组测试内，$\sum n$ 不会超过 $5 \times 10^5$。

输出格式

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

3
9