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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

多组数据,答案对 998244353 取模。

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

输入格式

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

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

输出格式

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

样例

样例输入 1

5
3
4
5
233
666

样例输出 1

1
2
3
134793965
35803200

数据范围与提示

测试点编号 T n 分值
1 =1 \leq 8 5
2 \leq 200
3
4 \leq 2000
5
6
7 = 66666
8 \leq 10^5
9
10
11
12
13 =10^5 40