题目背景

WD整日沉浸在积木中，无法自拔……

题目描述

WD想买 $n$ 块积木，商场中每块积木的高度都是 $1$，俯视图为正方形（边长不一定相同）。由于一些特殊原因，商家会给每个积木随机一个大小并标号，发给 WD。

接下来 WD 会把相同大小的积木放在一层，并把所有层从大到小堆起来。WD 希望知道所有不同的堆法中层数的期望。两种堆法不同当且仅当某个积木在两种堆法中处于不同的层中，由于WD只关心积木的相对大小，因此所有堆法等概率出现，而不是随机的大小等概率（可以看样例理解）。
输出结果 $\bmod \space 998244353$ 即可。

（如果还是不能够理解题意，请看样例）

输入格式

第一行一个数$T$，表示询问个数。

接下来 $T$ 行每行一个数 $n$，表示 WD 希望使用 $n$ 块积木。

输出格式

共 $T$ 行，每行一个数表示答案 $\bmod \space 998244353$。

4
1
2
3
4

1
665496237
307152111
186338949

提示

接下来用大括号表示分在一层。

对于$n=1$，合法的分法只有$\{1\}$；

对于$n=2$，合法的序列有$\{1,2\}$，$\{1\}\{2\}$，$\{2\}\{1\}$，期望层数为$\frac{1+2+2}{3}=665496237(mod~998244353)$；

对于$n=3$，合法的序列有$\{1\}\{2\}\{3\}$，$\{1\}\{3\}\{2\}$，$\{2\}\{1\}\{3\}$，$\{2\}\{3\}\{1\}$，$\{3\}\{1\}\{2\}$，$\{3\}\{2\}\{1\}$

$\{1,2\}\{3\}$，$\{1,3\}\{2\}$，$\{2,3\}\{1\}$，$\{1\}\{2,3\}$，$\{2\}\{1,3\}$，$\{3\}\{1,2\}$，$\{1,2,3\}$共13种。因此期望就是$\frac{6\times3+6\times2+1}{13}=307152111(mod~998244353)$

对于$n=4$，我想到了一个绝妙的解释，可惜这里写不下。

$subtask1(21pts):~1\le T\le 1,000,~1\le n\le 1,000$

$subtask2(37pts):~1\le T\le 10,~1\le n\le 100,000$

$subtask3(42pts):~1\le T\le 100,000,~1\le n\le 100,000$