[AdditionalFile6512.zip](file://AdditionalFile6512.zip?type=additional_file)

#6512. 「雅礼集训 2018 Day8」C

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

计算化学式为 ${\rm C}_n{\rm H}_{2n+2}$ 的烷烃的同分异构体个数。

多组数据，答案对 $998244353$ 取模。

提示：如果你不知道什么是烷烃，那么你可以认为这个问题等价于求 $n$ 个点的无标号无根树并满足每个点的度数 $\leq 4$ 的树的个数。

输入格式

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

接下来 $T$ 行，每行一个整数 $n$，表示询问化学式为 ${\rm C}_n{\rm H}_{2n + 2}$ 的烷烃的同分异构体个数。

输出格式

共输出 $T$ 行，每行一个整数，表示答案。

样例

输入

5
3
4
5
233
666

输出

1
2
3
134793965
35803200

数据范围与提示