Counting Forests with Exactly Two Merge Sequences

Consider the following union–find code snippet: [ \begin{aligned} inline\ int\ find(int\ x){
if(xfa[x]) return x;
return fa[x] = find(fa[x]);
}
inline\ void\ merge(int\ x, int\ y){
fx = find(x),\ fy = find(y);
if(fxfy)return;
fa[fx]=fy;
}
\end{aligned} ] Initially, for every $x$ we have (fa[x]=x). Over the next $T$ days, on each day you are given an integer $n$ (note that $n$ can vary each day) denoting the size of the union–find structure. When no one is around, mischievous Xiao X repeatedly performs the operation merge. However, note that he dislikes the equality operator (==) so much that he never executes the early return in the merge function (i.e. the condition if(fx==fy)return; is never triggered).

After all these merge operations, only the final array (fa) is known. Recall that each merge (which is never short–circuited) connects two disjoint sets; thus, if the union–find structure has several connected components, each component forms a tree $T$ in which the root $r$ satisfies (fa[r]=r) and for every non–root vertex (v) we have (fa[v]=p(v)) for some parent $p(v)$.

For any sequence of merge operations that produced a given final (fa) array one may “recover” the merge operations. Two merge operation sequences are considered different if and only if in some merge operation the pair of values ( (fx,fy) ) (computed by the find function) are not identical. For a fixed final (fa) array one may obtain a certain number (possibly one) of valid merge sequences.

Define $E(T)$ as the number of valid merge–operation sequences that yield a tree $T$ (when we view each merge as forming an edge directed from the child to its parent). One may prove that if $T$ is a chain (i.e. every non–root vertex has exactly one child) then (E(T)=1); otherwise, if $T$ is not a chain then (E(T)\ge 2). In fact, it turns out that $E(T)=2$ if and only if the tree $T$ is almost a chain, meaning that exactly one vertex in $T$ has two children and every other vertex has at most one child.

Now, a final (fa) array (or forest) is said to be recoverable in exactly two ways if when decomposing it into the trees of its connected components, exactly one tree has $E(T)=2$ and every other tree is a chain (thus having $E(T)=1$).

Your task is: for a given $n$, count the number of valid final (fa) arrays (i.e. forests on the set ({1,2,\dots,n}) that can occur from a sequence of merge operations as described) which are recoverable in exactly two different ways. Since the answer may be large, output it modulo (998244353).

It can be shown that the answer for each $n$ is given by [ \text{Answer}(n)= n!\cdot\Biggl(\sum_{k=3}^{n}\Bigl(\frac{k^{k-1}}{k!}\Bigr)- (n-2)\Biggr) \pmod{998244353}. ]

Input

The first line contains an integer $T$ ($T\ge 1$) denoting the number of days. Each of the next $T$ lines contains one integer $n$ ($1\le n\le N$) representing the size of the union–find array on that day.

Output

For each day, output one line containing a single integer: the number of valid final fa arrays recoverable in exactly two ways, modulo \(998244353\).

Explanation

For example, when n=3 the only non–chain tree on 3 vertices is the star (where the root has two children) and there are exactly 3 such trees. Hence the answer is 3. When n=2, every final array is a chain, so the answer is 0.

inputFormat

The first line contains an integer $T$, the number of test cases (days). Each of the next $T$ lines contains a single integer $n$.

outputFormat

For each test case, output a single integer: the number of valid final fa arrays that can be recovered in exactly two ways, modulo 998244353.

sample

4
2
3
4
5

0
3
52
765

</p>