CF1726E.Almost Perfect

A permutation $p$ of length $n$ is called almost perfect if for all integer $1 \leq i \leq n$, it holds that $\lvert p_i - p^{-1}_i \rvert \le 1$, where $p^{-1}$ is the inverse permutation of $p$ (i.e. $p^{-1}_{k_1} = k_2$ if and only if $p_{k_2} = k_1$).

Count the number of almost perfect permutations of length $n$ modulo $998244353$.

长度为 $n$ 的排列 $p$ 被称为几乎完美排列，当且仅当对所有整数 $1 \leq i \leq n$，均满足 $\lvert p_i - p^{-1}_i \rvert \le 1$，其中 $p^{-1}$ 是 $p$ 的逆排列（即：$p^{-1}_{k_1} = k_2$ 当且仅当 $p_{k_2} = k_1$）。

求长度为 $n$ 的几乎完美排列的个数，对 $998244353$ 取模。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of each test case follows.

The first and only line of each test case contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是每个测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示排列的长度。

保证所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each test case, output a single integer — the number of almost perfect permutations of length $n$ modulo $998244353$.

对于每个测试用例，输出一个整数——长度为 $n$ 的几乎完美排列的个数对 $998244353$ 取模的结果。

For $n = 2$, both permutations $[1, 2]$, and $[2, 1]$ are almost perfect.

For $n = 3$, there are only $6$ permutations. Having a look at all of them gives us:

• $[1, 2, 3]$ is an almost perfect permutation.
• $[1, 3, 2]$ is an almost perfect permutation.
• $[2, 1, 3]$ is an almost perfect permutation.
• $[2, 3, 1]$ is NOT an almost perfect permutation ($\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$).
• $[3, 1, 2]$ is NOT an almost perfect permutation ($\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$).
• $[3, 2, 1]$ is an almost perfect permutation.

So we get $4$ almost perfect permutations.

当 $n = 2$ 时，排列 $[1, 2]$ 和 $[2, 1]$ 均为几乎完美排列。

当 $n = 3$ 时，共有 $6$ 个排列。逐一检验所有排列可得：

• $[1, 2, 3]$ 是一个几乎完美排列。
• $[1, 3, 2]$ 是一个几乎完美排列。
• $[2, 1, 3]$ 是一个几乎完美排列。
• $[2, 3, 1]$ 不是一个几乎完美排列（$\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$）。
• $[3, 1, 2]$ 不是一个几乎完美排列（$\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$）。
• $[3, 2, 1]$ 是一个几乎完美排列。

因此，我们共得到 $4$ 个几乎完美排列。