暂无测试数据。

在小 O 的梦中，有一个长度为 $n$ 的序列 $A$ 和一个大小为 $n$ 的点集 ${1\cdots n}$ ，由于梦中的能量流动十分不稳定，序列 $A$ 的任意一位上都有可能是 $[1,n]$ 中的任意一个数，且概率均为 $\frac{1}{n}$

小 O 发现，一些点对开始有了联系，一对点 $(x,y)[x,y\in[1,n]]$ 间有一条无向边当且仅当 $A_x=y$ 或者 $A_y=x$ ，显然会有 $n$ 条边，构成了一张无向图，图中有一些能量，小 O 需要收集这些能量来获得点集的密码

然而，当一些点断开所有与它相连的边时，如果图的联通块个数增加了，即当这些点是割点时，图就会变得不稳定，小 O 就会难以收集能量

现在，小 O 已经知道了一些梦境中点集的大小，请你帮她算出这张图中期望有多少个不稳定的点，由于点数可能过大或者过小而导致 小 O 无法缩小范围，请将答案乘$n^n$后对$998244353$取模后告诉 小 O

输入格式

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

接下来 $T$ 行，每行一个数$n$，代表一个点集的大小。

输出格式

对于每次询问，输出一行，表示期望割点个数。

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n,T \leq 8$；

对于 $100\%$ 的数据，$1\leq n , T \leq 1000$。

5
1
2
3
4

0
0
15
280