J. Jorge likes "sum over all subarrays" problems
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jorge, as a dedicated ICPC participant, was upsolving the problems from the 2026 ICPC Gran Premio de Mexico 1ra Fecha contest. The last problem he upsolved was $$$F(x,l,r)$$$, a problem that asks contestants to find the sum of a function over all subarrays of a given array. Immediately after he finished upsolving, he started thinking about more problems that ask for the sum of a function over all subarrays, and he came up with the following problem:

For a given array $$$A=[a_1,a_2,\dots,a_n]$$$, Jorge defines $$$F(l,r)$$$ as:

$$$$$$ F(l,r)=\prod_{i=l}^r a_i $$$$$$

Jorge defines the value of the array $$$A$$$ as the sum of $$$F(l,r)$$$ over all its subarrays:

$$$$$$ \sum_{l=1}^n \sum_{r=l}^n F(l,r) $$$$$$

Jorge immediately found the answer to this problem, so he thought that it was too easy. Then he thought, "What if we now find the sum of the values of all permutations of length $$$n$$$?" This problem is not as trivial as Jorge thought, so he asks you to solve it.

You are given an integer $$$n$$$. Help Jorge find the sum of the values of all permutations of the integers $$$1,2,\dots,n$$$. Since the answer might be huge, find it modulo $$$998244353$$$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$)  — the number of test cases.

Each test case consists of a single line with an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the length of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a line with an integer  — the answer to the problem modulo $$$998244353$$$.

Example
Input
5
1
2
3
5
100
Output
1
10
116
41532
586129619
Note

Remember to upsolve all the problems!