F. The Forgotten Player
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ players in the academy, numbered from $$$1$$$ to $$$n$$$. To practice quick decision-making, they introduce a drill with the following rules:

  • Initially, each player has exactly one ball.
  • Each player must pass their ball exactly once.
  • A player must pass the ball to another player (passing to themselves is not allowed).
  • After all passes are made, a player may receive balls from multiple teammates or from none.
  • A player is called forgotten if they do not receive a ball from any player.

Your task is to determine the number of possible passing arrangements such that exactly one player is forgotten.

Since the answer may be large, print it modulo $$$998\,244\,353$$$.

Input

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

Output

For each test case, output the number of valid passing arrangements modulo $$$998\,244\,353$$$.

Example
Input
3
2
3
4
Output
0
6
48
Note

For $$$n = 2$$$, no valid passing arrangements exist.

For $$$n = 3$$$, all valid passing arrangements where exactly one player receives no ball are as follows:

  • $$$1 \to 2$$$, $$$2 \to 1$$$, $$$3 \to 1$$$
  • $$$1 \to 2$$$, $$$2 \to 1$$$, $$$3 \to 2$$$
  • $$$1 \to 2$$$, $$$2 \to 3$$$, $$$3 \to 2$$$
  • $$$1 \to 3$$$, $$$2 \to 1$$$, $$$3 \to 1$$$
  • $$$1 \to 3$$$, $$$2 \to 3$$$, $$$3 \to 1$$$
  • $$$1 \to 3$$$, $$$2 \to 3$$$, $$$3 \to 2$$$

Thus, we have a total of $$$6$$$ possible ways.