集合划分计数

题目描述

一个有 $n$ 个元素的集合,将其分为任意个非空子集,求方案数。 注意划分出的集合间是无序的,即 $\{\{1,2\},\{3\}\}$ 和 $\{\{3\},\{2,1\}\}$ 算作一种方案。 由于答案可能会很大,所以要对 $998244353$ 取模。

输入输出格式

输入格式


第一行一个正整数 $T$,表示数据组数。 接下来 $T$ 行,每行一个正整数 $n$。

输出格式


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

输入输出样例

输入样例 #1

5
2
3
7
9
233

输出样例 #1

2
5
877
21147
53753544

说明

【数据范围】 $T = 1000$,$1\le n \le 10^5$。 【样例解释】 对于 $n=3$,有五种方案:$\{\{1,2,3\}\},\{\{1,2\},\{3\}\},\{\{1\},\{2,3\}\},\{\{1\},\{2\},\{3\}\},\{\{1,3\},\{2\}\}$。 本题只有一个测试点,假设你答对了 $x$ 组数据,你将得到 $\lfloor x/(T/100) \rfloor$ 分。 如果你不能解决所有数据,也请输出 $T$ 个整数。 ~~TLE不要怪我,是你常数太大了~~