「雅礼集训 2018 Day8」C

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入

5
3
4
5
233
666

输出

1
2
3
134793965
35803200

数据范围与提示

注意：对于所有数据，保证 $1 \leq T \leq 10^5$，$1 \leq n \leq 10^5$。