Description

Compute the number of cycles in the undirected complete graph on $n$ vertices after deleting one edge, and output the answer modulo $998244353$.

Note: A “cycle” means choosing any vertex as the starting point, following non-repeating edges, visiting non-repeating vertices along the way, and then returning to the starting vertex to form a closed path.

Input Format

The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain an integer $n$, as described above.

Output Format

Output $T$ lines, each containing one integer, representing the answer.

4
3
4
5
6

0
3
22
133

Hint

For the first $10\%$ of the testdata, $3 \leq n \leq 10$.

For an additional $20\%$ of the testdata, $9.99\times 10^2 \leq n \leq 10^3$.

For an additional $30\%$ of the testdata, $9.99\times 10^4 \leq n \leq 10^5$.

For the remaining $40\%$ of the testdata, $9.99\times 10^8 \leq n \leq 10^9$.

All testdata satisfy $1 \leq T \leq 10$.

Translated by ChatGPT 5