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 \lt j$ and $a_i \gt 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$.

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