题目背景

syzf2222 喜欢并查集！特别是路径压缩的并查集。

题目描述

inline int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	fx=find(x),fy=find(y);
	if(fx==fy)return;fa[fx]=fy;
}

这是他惯用的并查集代码，初始时对于每个 $x$ 有 fa[x]=x。

接下来的 $T$ 天中，每天小 h 都给了他一个 $n$，表示并查集的大小（每天的 $n$ 可能是不同的）。

调皮的小 x 见他不在机房，每天都在并查集上不断 merge。 注意到小 x 不喜欢 ==，他觉得这特别像他的眼睛，于是他不会使 merge 函数在第二行的条件语句中被 return，否则他会十分气愤。

现在的已知信息就只有最终的 $fa$ 数组了。 而 syzf2222 希望还原小 x 的操作序列（即若干次按顺序进行的 merge 操作）。由于他名字里有很多个 2 而且本人也非常 2 ，他希望知道对于每一天，有多少个 $fa$ 数组恰好能被还原成两种操作序列，答案对 $998244353$ 取余数。

两个操作序列不同，当且仅当某次 merge 时的变量 fx,fy 至少有一个不同。

输入格式

第一行一个整数 $T$。

后面 $T$ 行，每行读入一个整数 $n$ 表示小 h 给的数。

输出格式

$T$ 行，每行一个整数表示答案对 $998244353$ 取余数的结果。

4
3
20
8492
114514

3
61560
822256526
988192964

提示

【样例解释】

对于第一天，$n=3$，共有 $fa=[1,1,1],[2,2,2],[3,3,3]$ 这三种 $fa$ 数组使得恰有两种操作序列。

以 $fa=[1,1,1]$ 为例，两种操作序列分别为 merge(2,1),merge(3,1) 和 merge(3,1),merge(2,1)，其他 merge 参数不同的方案与上述两种的其中一种是本质相同的（每次的 fx,fy 都一样）。

【数据范围】

「本题采用捆绑测试」

• $\texttt{Subtask 1(10 pts)：}T=1,\ n\le 10$；
• $\texttt{Subtask 2(30 pts)：}T=10^2,\ n\le 10^3$；
• $\texttt{Subtask 3(60 pts)：}$无特殊限制。

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