Problem Description

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}$.

1
2

40