write a go solution for E. Shohag Loves Inversionstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputShohag 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^∗ 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: [textbf3,4,6,2,4], [4,textbf3,6,2,4], [4,6,textbf3,2,4], [4,6,2,textbf3,4], and [4,6,2,4,textbf3].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.^∗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.InputThe first line contains a single integer t (1<=t<=10^4) — the number of test cases.The first and only line of each test case contains an integer n (2<=n<=10^6).It is guaranteed that the sum of n over all test cases does not exceed 10^6.OutputFor each test case, output an integer — the number of possible arrays modulo 998,244,353.ExampleInput442769Output5
1
682
325188814
NoteIn the first test case, the following 5 arrays can be obtained (the inserted inversion count is shown in bold):  [0,1]arrow[0,textbf0,1]arrow[0,0,1,textbf0],  [0,1]arrow[0,textbf0,1]arrow[0,0,textbf0,1],  [0,1]arrow[0,1,textbf0]arrow[0,1,0,textbf1],  [0,1]arrow[0,1,textbf0]arrow[0,1,textbf1,0],  [0,1]arrow[0,1,textbf0]arrow[textbf1,0,1,0].. Output only the code with no comments, explanation, or additional text.