E. Shohag Loves Inversions
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Shohag has an array $$$a$$$ of integers. Initially $$$a = [0, 1]$$$. He can repeatedly perform the following operation any number of times:

  • Let $$$k$$$ be the number of inversions$$$^{\text{∗}}$$$ in the current array $$$a$$$.
  • Insert $$$k$$$ at any position in $$$a$$$, including the beginning or the end.

For example, if $$$a = [4, 6, 2, 4]$$$, then the number of inversions is $$$k = 3$$$. So Shohag can obtain the following arrays after the operation: $$$[\textbf{3}, 4, 6, 2, 4]$$$, $$$[4, \textbf{3}, 6, 2, 4]$$$, $$$[4, 6, \textbf{3}, 2, 4]$$$, $$$[4, 6, 2, \textbf{3}, 4]$$$, and $$$[4, 6, 2, 4, \textbf{3}]$$$.

Given an integer $$$n$$$, help Shohag count, modulo $$$998\,244\,353$$$, the number of distinct arrays of length $$$n$$$ that can be obtained after performing the operations.

$$$^{\text{∗}}$$$The number of inversions in an array $$$a$$$ is the number of pairs of indices ($$$i$$$, $$$j$$$) such that $$$i < j$$$ and $$$a_i > a_j$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output an integer — the number of possible arrays modulo $$$998\,244\,353$$$.

Example
Input
4
4
2
7
69
Output
5
1
682
325188814
Note

In the first test case, the following $$$5$$$ arrays can be obtained (the inserted inversion count is shown in bold):

  • $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, 1, \textbf{0}]$$$,
  • $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, \textbf{0}, 1]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, 0, \textbf{1}]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, \textbf{1}, 0]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [\textbf{1}, 0, 1, 0]$$$.