E. Shohag 喜欢逆序对
每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

$Shohag$ 有一个整数数组 $a$。初始时 $a = [0, 1]$。
他可以重复进行以下操作任意次：

设 $k$ 为当前数组 $a$ 中逆序对$^{*}$的数量。
将 $k$ 插入到 $a$ 的任意位置（包括开头和结尾）。

例如，若 $a = [4,6,2,4]$，则逆序对数量为 $k = 3$。
因此，在一次操作后，Shohag 可以得到以下数组：
$[3,4,6,2,4]$，$[4,3,6,2,4]$，$[4,6,3,2,4]$，$[4,6,2,3,4]$，$[4,6,2,4,3]$。

给定一个整数 $n$，请帮助 $Shohag$ 计算：通过若干次操作后，能够得到的所有长度为 $n$ 的不同数组的数量，结果对 $998244353$ 取模。

$^{*}$ 一个数组 $a$ 中的逆序对数量是指满足 $i < j$ 且 $a_i > a_j$ 的索引对 $(i, j)$ 的数量。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据的组数。
每组测试数据仅有一行，包含一个整数 $n$（$2 \le n \le 10^6$）。
保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出
对于每组测试数据，输出一个整数 —— 可能得到的不同数组的数量，对 $998244353$ 取模。

示例
输入

4
4
2
7
69

输出

5
1
682
325188814

提示
在第一个测试数据中（$n = 4$），可以得到以下 $5$ 个数组（插入的逆序对数用粗体标出）：

$[0,1] \to [0,\mathbf{0},1] \to [0,0,1,\mathbf{0}]$，
$[0,1] \to [0,\mathbf{0},1] \to [0,0,\mathbf{0},1]$，
$[0,1] \to [0,1,\mathbf{0}] \to [0,1,0,\mathbf{1}]$，
$[0,1] \to [0,1,\mathbf{0}] \to [0,1,\mathbf{1},0]$，
$[0,1] \to [0,1,\mathbf{0}] \to [\mathbf{1},0,1,0]$。