P17624 [qaswed12 OI R1] BrrTree
题目背景
Brr Brr patapim 是一只意大利山海经动物。
题目描述
我们定义一颗 brr 树为叶节点数严格大于总节点数二分之一且以 $1$ 为根的**有标号**树。
给定 $T$ 组数据，每组数据给定一个整数 $n$。
请你求出本质不同的，有 $n$ 个节点的 brr 树的数量，答案对 $998244353$ 取模。
两棵 brr 树本质不同当且仅当，存在点 $i$ 和点 $j$ 在**恰好**其中一棵 brr 树中有连边。
某个点为叶子节点当且仅当其没有儿子节点。
输入格式
第一行一个整数 $T$ 表示询问组数。
接下来 $T$ 行，每行一个正整数 $n$。
输出格式
共 $T$ 行，每行一个整数表示答案。
说明/提示
### 样例解释
当 $n=2$ 时显然无解。
当 $n=3$ 时，$2,3$ 均为 $1$ 的儿子结点显然为一组解。
当 $n=5$ 时，对于形态如下的树，各有 $1,4,12,12$ 种：
其中 $a,b,c,d$ 是 $2,3,4,5$ 的一个排列。
于是答案为 $1+4+12+12=29$ 种。
**注意本题要求本质不同的树，即如下两棵树算作相同：**
### 数据范围与约定
**本题开启捆绑测试，请注意本题特殊的时间限制。**
|子任务编号|$n \le$|分值|
|:--------:|:--------:|:--------:|
|$1$|$6$|$10$|
|$2$|$10$|$15$|
|$3$|$20$|$20$|
|$4$|$2000$|$20$|
|$5$|$10^{5}$|$35$|
对于 $100\%$ 的数据，满足 $1 \le T \le 10$，$1 \le n \le 10^{5}.$