Background

WD is immersed in building blocks all day and cannot stop...

Problem Description

WD wants to buy $n$ building blocks. In the store, each block has height $1$, and its top view is a square (the side length is not necessarily the same). For some special reasons, the seller will randomly assign each block a size and a label, and give them to WD.

Next, WD will put blocks of the same size into one layer, and stack all layers from large to small. WD wants to know the expected number of layers among all different stacking methods. Two stacking methods are different if and only if some block is in a different layer in the two methods. Since WD only cares about the relative sizes of the blocks, all stacking methods are equally likely, rather than all random size assignments being equally likely (you can understand this from the samples).
Output the result $\bmod \space 998244353$.

(If you still cannot understand the statement, please look at the samples.)

Input Format

The first line contains an integer $T$, the number of queries.

Then follow $T$ lines, each containing an integer $n$, meaning WD wants to use $n$ building blocks.

Output Format

Output $T$ lines. Each line contains one integer, the answer $\bmod \space 998244353$.

4
1
2
3
4

1
665496237
307152111
186338949

Hint

In the following, curly braces denote blocks placed in the same layer.

For $n=1$, the only valid arrangement is $\{1\}$.

For $n=2$, the valid sequences are $\{1,2\}$, $\{1\}\{2\}$, $\{2\}\{1\}$. The expected number of layers is $\frac{1+2+2}{3}=665496237(mod~998244353)$.

For $n=3$, the valid sequences are $\{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\}$, for a total of 13 types. Therefore, the expectation is $\frac{6\times3+6\times2+1}{13}=307152111(mod~998244353)$.

For $n=4$, I have a wonderful explanation, but unfortunately there is not enough space to write it here.

$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$

Translated by ChatGPT 5