Expected Weight

 Given a sequence 

A$A$ of length N$N$, the weight of this sequence is defined as

weight(A)=∑i=1Ni⋅Ai$$\text{weight}(A)=\sum _{i=1}^{N}i\cdot A_i$$

Given an integer N$N$, we pick a permutation A$A$ of [1,2…N]$[1,2\dots N]$ uniformly at random. What is the expected weight of this permutation?

It can be shown that the answer can be represented as PQ${\displaystyle \frac{P}{Q}}$ where P$P$ and Q$Q$ are coprime integers and Q≠0(mod998244353)$Q\ne 0(\mathrm{mod}998244353)$. Print the value of P⋅Q−1$P\cdot Q^{-1}$ modulo 998244353$998244353$.

Input Format

• First line of the input contains T$T$, the number of test cases. Then the test cases follow.
• Each test case contains a single integer on a single line N$N$.

Output Format

For each test case, print a single integer, the answer to the test case.

Constraints

• 1≤T≤2⋅105$1\le T\le 2\cdot {10}^5$
• 1≤N≤109$1\le N\le {10}^9$

Subtasks

• Subtask 1 (100 points): Original constraints

Sample Input 1 

3
1
2
3

Sample Output 1 

1
499122181
12

Explanation

• Test case 1$1$: There is only one permutation of [1]$[1]$ which is [1]$[1]$ and the weight of this permutation is equal to 1$1$. So, the expected weight is equal to 1$1$.
• Test case 2$2$: There are 2$2$ permutations of [1,2]$[1,2]$ namely
• [1,2]$[1,2]$ with weight equal to 5$5$.
• [2,1]$[2,1]$ with weight equal to 4$4$.

So, the expected weight is equal to 5+42!=92$\frac{5+4}{2!}=\frac{9}{2}$.

• Test case 3:$3:$ There are 6$6$ permutations of [1,2,3]$[1,2,3]$ namely
• [1,2,3]$[1,2,3]$ with weight equal to 14$14$.
• [1,3,2]$[1,3,2]$ with weight equal to 13$13$.
• [2,1,3]$[2,1,3]$ with weight equal to 13$13$.
• [2,3,1]$[2,3,1]$ with weight equal to 11$11$.
• [3,1,2]$[3,1,2]$ with weight equal to 11$11$.
• [3,2,1]$[3,2,1]$ with weight equal to 10$10$.

So, the expected weight is equal to 14+13+13+11+11+103!=12$\frac{14+13+13+11+11+10}{3!}=12$.