P3862 Counting Cycles

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.

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 $T$ lines, each containing one integer, representing the answer.

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