U237806 【模板】错位排列问题
题目描述
对于一个长度为 $n$ 的排列 $A$，如果满足对于任意的 $i$，$A_i \neq i$，那我们称这个排列是错位排列，简称错排。
给出长度 $n$，你需要计算所有长度为 $n$ 的排列中，有多少个错排？答案可能很大，你只需要对 $998244353$ 取模即可。
输入格式
第一行一个整数 $T$，表示数据组数。
以下 $T$ 行，每行一个整数 $n$。
输出格式
$T$ 行，每行一个整数，表示答案（记得取模）。
说明/提示
| 子任务 | 分值 | 时间限制 | 数据范围 |
| :----------: | :----------: | :----------: | :----------: |
| $\texttt{Subtask \#1}$ | $20$ | $0.5s$ |$\mathbf{0} \le n \leq 10^3,1 \leq T \leq 10^5$ |
| $\texttt{Subtask \#2}$ | $80$ | $1.0s$ |$\mathbf{0} \le n \leq 10^7,1 \leq T \leq 10^6$ |
参考时间复杂度 $O(\max\{n\}+T)$。