CF2039E Shohag Loves Inversions

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

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

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

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