C. Perfect Square Matrix
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an $$$n \times n$$$ square matrix. At first, all elements in this matrix are zero.

You need to change $$$n$$$ elements in the matrix so that $$$1,2, \ldots ,n$$$ appears exactly once.

A square matrix of size $$$n \times n$$$ is considered perfect if its number of good square submatrices reaches maximum. A square submatrix of size $$$m \times m (m \le n)$$$ is considered good if it contains the integer $$$m$$$.

Count the number of possible perfect square matrices. Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$  — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ $$$(2 \le n \le 10^6)$$$  — the size of the matrix.

It's guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^6$$$.

Output

For each testcase, output in a new line  — the answer modulo $$$998\,244\,353$$$.

Example
Input
4
2
3
5
999990
Output
12
56
25872
492008352
Note

In the first test case, you can freely select two elements and change them into $$$1$$$ and $$$2$$$. All matrices obtained using this method are perfect. Thus, the answer is $$$A^{4}_{2}=12$$$.

For example,

12
00

is perfect. Its number of good square submatrices reaches the maximum $$$2$$$. It has one $$$1 \times 1$$$ good square submatrix and one $$$2 \times 2$$$ good square submatrix.

In the second test case, for example,

100
020
003

is perfect. Its number of good square submatrices reaches the maximum $$$6$$$. It has one $$$1 \times 1$$$ good square submatrix, four $$$2 \times 2$$$ good square submatrices, and one $$$3 \times 3$$$ good square submatrix.