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

$\text{weight}(A) = \sum_{i = 1}^{N} i\cdot A_{i}$

Given an integer N, we pick a permutation A of $[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 $\displaystyle \frac{P}{Q}$ where P and Q are coprime integers and $Q \neq 0 \pmod{998244353}$. Print the value of $P \cdot Q^{-1} modulo 998244353$.

------ Input Format ------

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

------ Output Format ------

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

------ Constraints ------

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N ≤ 10^{9}$

------ subtasks ------

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------
3
1
2
3

----- Sample Output 1 ------
1
499122181
12

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

So, the expected weight is equal to $\frac{5 + 4}{2!} = \frac{9}{2}$.
- Test case $3:$
There are $6$ permutations of $[1, 2, 3]$ namely
- $[1, 2, 3]$ with weight equal to $14$.
- $[1, 3, 2]$ with weight equal to $13$.
- $[2, 1, 3]$ with weight equal to $13$.
- $[2, 3, 1]$ with weight equal to $11$.
- $[3, 1, 2]$ with weight equal to $11$.
- $[3, 2, 1]$ with weight equal to $10$.

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

见题面

见题面