A. Matrix
time limit per test
1.0 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Fill an $$$n\times n$$$ matrix with numbers in $$$[1,n^2]$$$, where each number occurs exactly once.

For a fixed number filling method, let $$$a_i$$$ be the mininum number in the $$$i$$$th row, and $$$S=\{a_1,a_2,...,a_n\}\cap\{1,2,...,n\}$$$.

You need to calculate $$$\sum |S|\pmod {998244353}$$$, i.e. the sum of the size of $$$S$$$ over all possible methods.

Input

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 30$$$).

Then $$$T$$$ cases follow, each of which contains a single interger $$$n$$$ ($$$1\leq n\leq 5000$$$).

Output

For each test case, output one line contains the value of $$$\sum |S|\pmod {998244353}$$$.

Example
Input
1
2
Output
40