seuOJ233 - 化学题

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2019

题目描述

小明在上化学课，老师给他布置了三道化学题：

1. 求 $2$ 个碳的烷烃有多少个同分异构体。
2. 求 $3$ 个碳的烷烃有多少个同分异构体。
3. 求 $N$ 个碳的烷烃有多少个同分异构体。

小明决定把问题交给你，由于答案可能很大，答案对 $998244353$ 取模。

PS：如果不知道什么是烷烃，什么是同分异构体，问题可以抽象为如下模型：求 $N$ 个点，每个点度数不超过 $4$ 的无根树有多少个（只考虑形状，不考虑编号）。

输入格式

第一行一个整数 $T(1 \leq T \leq 20)$ ，表示 $T$ 组数据。
接下来 $T$ 行，每行一个整数 $N(1 \leq N \leq 10^3)$。

输出格式

输出 $T+2$ 行，每行一个整数。
第一行为问题1的答案。
第二行为问题2的答案。
接下来 $T$ 行，对于每个 $N$ 输出问题3答案，。

样例

样例输入

3
4
5
6

样例输出

1
1
2
3
5