Almost Perfect
Description
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$.
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$.
For each test case, output a single integer — the number of almost perfect permutations of length $n$ modulo $998244353$.
Input
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$.
Output
For each test case, output a single integer — the number of almost perfect permutations of length $n$ modulo $998244353$.
3
2
3
50
2
4
830690567
Note
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.