For a given integer $n$ as the length of an arbitrary permutation $p$ indexed from $1$ to $n$, find the maximum value of $\sum_{1 \le l \le r \le n} \mathrm{mex}(a[l,r])$.

A permutation of length $n$ is an array of length $n$ that each elements of this array is not less than $1$ and not greater than $n$, and each number appears exactly once. $a[l,r]$ denotes the subarray of $a$ from $l$ to $r$.

$\mathrm{mex}$ is a function that for an input array $a$, $\mathrm{mex}(a)$ returns the minimum positive integer that does not appear in array $a$.

The input contains $T$ testcases, the first line is an integer $T$ $(1 \le T \le 10^5)$, denoting the number of testcases.

For each test case, the input contains only one integer $n$ $(1 \le n \le 10^9)$ in one line, denoting $n$ as the length of the permutation $p$.

For each testcase, output one integer in one line, denoting the answer. Since this number maybe very large, output the maximum value modulo $998244353$.

For the second test case, given the inputs $n = \{16707, 62135, 1000000\}$, the answers are $\{388854427453, 19994062579602, 83334208334250000\}$.

Therefore, the outputs are ${537374136, 226433365, 99413837}$ after applying modulo operation with $998244353$.