题目描述

计算化学式为 ${\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

数据范围与提示