Description

Given a set with $n$ elements, split it into any number of non-empty subsets, and find the number of possible ways.

Note that the resulting subsets are unordered. That is, $\{\{1,2\},\{3\}\}$ and $\{\{3\},\{2,1\}\}$ are considered the same partition.

Since the answer may be very large, output it modulo $998244353$.

Input Format

The first line contains a positive integer $T$, which indicates the number of test cases.
The next $T$ lines each contain a positive integer $n$.

Output Format

Output $T$ lines, each containing one integer representing the answer.

5
2
3
7
9
233

2
5
877
21147
53753544

Hint

Constraints
$T = 1000$, $1 \le n \le 10^5$.

Sample Explanation
For $n=3$, there are five ways: $\{\{1,2,3\}\},\{\{1,2\},\{3\}\},\{\{1\},\{2,3\}\},\{\{1\},\{2\},\{3\}\},\{\{1,3\},\{2\}\}$.

This problem has only one test point. Suppose you answer $x$ test cases correctly, you will get $\lfloor x/(T/100) \rfloor$ points.
If you cannot solve all the test cases, please still output $T$ integers.

Do not blame me for TLE. Your constant factor is too large.

Translated by ChatGPT 5