题目描述

一个有 $n$ 个元素的集合，将其分为任意个非空子集，求方案数。 注意划分出的集合间是无序的，即 $\{\{1,2\},\{3\}\}$ 和 $\{\{3\},\{2,1\}\}$ 算作一种方案。

由于答案可能会很大，所以要对 $998244353$ 取模。

输入格式

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

输出格式

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

样例 #1

样例输入 #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不要怪我，是你常数太大了