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.
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$$$).
For each test case, output one line contains the value of $$$\sum |S|\pmod {998244353}$$$.
1 2
40