Let $p = (p_1, p_2, \ldots, p_n)$ be a permutation of $\{1, 2, \ldots, n\}$.
For every index $1 \le i \le n$, define

The funniness of a permutation $p$ is

Given $n$, compute

where $S_n$ is the set of all $n!$ permutations of $\{1, 2, \ldots, n\}$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^6$), the number of test cases.

Each of the next $t$ lines contains a single integer $n$ ($1 \le n \le 10^6$).

Output

For each test case, print a single line containing $\sum_{p \in S_n} f(p)$ modulo $998\,244\,353$.

Exemplul 1

stdin

3
3
10
2048

stdout

998244352
108328320
887633861

Note

In the first test case, $n = 3$. The six permutations of $\{1, 2, 3\}$ are:

For example, in $p = (3, 1, 2)$, the nearest element to the left of position $3$ that is greater than $p_3 = 2$ is $p_1 = 3$, so $\operatorname{pg}(3) = 1$.

The total is $-3 + 0 - 1 + 0 + 1 + 2 = -1$, and $-1 \equiv 998\,244\,352 \pmod{998\,244\,353}$.