Shohag Loves Inversions

给你一个数列，初始数列为 $ a = [0, 1] $ ，现在重复进行以下操作若干次:

• 将当前数组中逆序对个数k插入当前数组中任意一个位置，包括开头或者结尾。

举个例子, 如果 $ a = [4, 6, 2, 4] $ , 则逆序对个数是 $ k = 3 $ . 所以可以通过操作，得到以下数组: $ [\textbf{3}, 4, 6, 2, 4] $ , $ [4, \textbf{3}, 6, 2, 4] $ , $ [4, 6, \textbf{3}, 2, 4] $ , $ [4, 6, 2, \textbf{3}, 4] $ , 和$ [4, 6, 2, 4, \textbf{3}] $ 。

给一个整数 $ n $，求通过操作可以得到多少种长度为$ n $的不同数列，方案数对对 $ 998,244,353 $ 取模。

逆序对的对数就是有多少个二元组，满足 $ i < j $ 并且 $ a_i > a_j $ 。

第一行给出一个整数$ t $ ( $ 1 \le t \le 10^4 $ )，表示有多少组数据。

每行给出一个整数 $ n $ ( $ 2 \le n \le 10^6 $ )

可以保证n的和在所有测试用例中不超过$ 10^6 $ 。

对于每一个测试点, 输出一个整数 — 对 $ 998,244,353 $ 取模。

样例 #1

样例输入 #1

4
4
2
7
69

样例输出 #1

5
1
682
325188814

对于第一个样例, 以下$ 5 $种数列可以通过操作得到

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