{"raw_statement":[{"iden":"background","content":"syzf2222 喜欢并查集！特别是路径压缩的并查集。"},{"iden":"statement","content":"\n\n```cpp\ninline int find(int x){\n\tif(x==fa[x])return x;\n\treturn fa[x]=find(fa[x]);\n}\ninline void merge(int x,int y){\n\tfx=find(x),fy=find(y);\n\tif(fx==fy)return;fa[fx]=fy;\n}\n```\n\n这是他惯用的并查集代码，初始时对于每个 $x$ 有 `fa[x]=x`。\n\n接下来的 $T$ 天中，每天小 h 都给了他一个 $n$，表示并查集的大小（每天的 $n$ 可能是不同的）。\n\n调皮的小 x 见他不在机房，每天都在并查集上不断 `merge`。\n注意到小 x 不喜欢 `==`，他觉得这特别像他的眼睛，于是他不会使 `merge` 函数在第二行的条件语句中被 `return`，否则他会十分气愤。\n\n现在的已知信息就只有最终的 $fa$ 数组了。\n而 syzf2222 希望还原小 x 的操作序列（即若干次按顺序进行的 `merge` 操作）。由于他名字里有很多个 2 而且本人也非常 2 ，他希望知道对于每一天，有多少个 $fa$ 数组**恰好**能被还原成**两种**操作序列，答案对 $998244353$ 取余数。\n\n两个操作序列不同，当且仅当某次 `merge` 时的变量 `fx,fy` 至少有一个不同。\n\n"},{"iden":"input","content":"第一行一个整数 $T$。\n\n后面 $T$ 行，每行读入一个整数 $n$ 表示小 h 给的数。"},{"iden":"output","content":"$T$ 行，每行一个整数表示答案对 $998244353$ 取余数的结果。"},{"iden":"note","content":"【样例解释】\n\n对于第一天，$n=3$，共有 $fa=[1,1,1],[2,2,2],[3,3,3]$ 这三种 $fa$ 数组使得恰有两种操作序列。\n\n以 $fa=[1,1,1]$ 为例，两种操作序列分别为 `merge(2,1),merge(3,1)` 和 `merge(3,1),merge(2,1)`，其他 `merge` 参数不同的方案与上述两种的其中一种是本质相同的（每次的 `fx,fy` 都一样）。\n\n---\n\n【数据范围】\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：}T=1,\\ n\\le 10$；\n- $\\texttt{Subtask 2(30 pts)：}T=10^2,\\ n\\le 10^3$；\n- $\\texttt{Subtask 3(60 pts)：}$无特殊限制。\n\n对于 $100\\%$ 的数据，满足 $1\\le T\\le 10^5,\\ 1\\le n\\le 10^9$。"}],"translated_statement":null,"sample_group":[["4\n3\n20\n8492\n114514","3\n61560\n822256526\n988192964\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}