题目描述

初始数组为 $[0,1]$。你可以反复执行如下操作：

设当前数组的逆序对数量为 $k$，你需要把整数 $k$ 插入到数组的任意一个位置。

给定目标长度 $n$，请计算能够通过上述操作得到多少个不同的长度为 $n$ 的数组。答案对 $998244353$ 取模。

这里，数组中一对下标 $(i,j)$ 是逆序对，当且仅当 $i<j$ 且 $a_i>a_j$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据一行一个整数 $n$。

输出格式

对每组数据输出一行一个整数，表示可能数组数量对 $998244353$ 取模后的结果。

样例

4
4
2
7
69

5
1
682
325188814

说明

第一个测试点中，长度为 $4$ 的数组共有 $5$ 个。样例说明中插入的逆序对数量用加粗位置表示。

数据范围

$1\le t\le10^4$，$2\le n\le10^6$。

所有测试组的 $n$ 之和不超过 $10^6$。