题目描述

樟老师曾经和自己最得意的弟子斯多克在办公室决斗。

斯多克占领了高地过后，樟老师大喊：反正我是不要紧的，你占领了高地那只有你会社会性死亡！

说完就奋不顾身用自己的血肉之躯拖住斯多克的纳米羽绒服，从头上扣出无数把辟邪手里剑向他掷去。

你现在是踏入地下八层办公室前一秒的斯多克，世界又给了你一次机会。

众所周知，樟是树。想要摸清楚樟老师的脑回路，最好研究清楚树的结构（智将）。

门后面是那座高地，是你不愿再想起，再体验的无尽的轮回中无尽的辟邪手里剑，你悲伤地想着。

你还有最后一秒钟，问题已经摆在眼前。在办公室里几乎无限的选择枝间，愿篝火照亮你唯一的前路。

给出长度为 $n$ 的排列 $p_{1\sim n}$，你需要计数满足下面条件的 $n$ 点带标号无根树的数量：

• 如果存在树边 $(i,j)$，也存在树边 $(p_i,p_j)$。

答案对 $998244353$ 取模。一个测试点中有多组数据。

输入格式

第一行，一个整数 $T$，表示数据组数。

每组数据的第一行，一个整数 $n$，表示排列长度。

每组数据的第二行，$n$ 个整数，表示 $p_{1\sim n}$。

输出格式

$T$ 行 $T$ 个整数，表示答案。

数据范围

对于 100% 的数据，满足 $1\le T,\sum n\le 5\times 10^5$。

测试点编号	$\sum n$	特殊性质
$1\sim 3$	$\le 50$，且 $n\le 8$	无
$4$	$\le 5\times 10^5$	A
$5$		BC
$6\sim 7$		BD
$8\sim 10$		D
$11\sim 14$	$\le 114$	无
$15\sim 20$	$\le 5\times 10^5$

特殊性质 A：$p_i = i$。

特殊性质 B：一定不存在 $p_i = i$。

特殊性质 C：如果存在 $p_i=j$，则 $p_j\neq i$。

特殊性质 D：如果存在 $p_i=j$，则 $p_j = i$。

输入样例 1

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

输出样例 1

0
5
1
4

输入样例 2

1
19
11 8 4 10 17 6 12 9 14 13 16 7 15 2 19 18 5 1 3

输出样例 2

1625

样例解释

对于样例 $1$：

对于第二组数据，一个满足条件的边集为：$\{(1,4),(2,5),(3,4),(4,5)\}$。

对于第三组数据，唯一满足条件的树的边集为：$\{(1,2),(1,3)\}$。

对于第四组数据，满足条件的边集为：$\{(1,2),(1,3),(2,4)\},\{(1,2),(1,4),(2,3)\},\{(1,3),(2,4),(3,4)\},\{(1,4),(2,3),(3,4)\}$。