[Solution] Almost Perfect Codeforces Solution

E. Almost Perfect

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A permutation 𝑝$p$ of length 𝑛$n$ is called almost perfect if for all integer 1≤𝑖≤𝑛$1\le i\le n$, it holds that |𝑝𝑖−𝑝−1𝑖|≤1$|p_i-p_i^{-1}|\le 1$, where 𝑝−1$p^{-1}$ is the inverse permutation of 𝑝$p$ (i.e. 𝑝−1𝑘1=𝑘2$p_{k_1}^{-1}=k_2$ if and only if 𝑝𝑘2=𝑘1$p_{k_2}=k_1$).

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

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 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≤𝑛≤3⋅105$1\le n\le 3\cdot {10}^5$) — the length of the permutation.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Output

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

Note

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

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

• [1,2,3]$[1,2,3]$ is an almost perfect permutation.
• [1,3,2]$[1,3,2]$ is an almost perfect permutation.
• [2,1,3]$[2,1,3]$ is an almost perfect permutation.
• [2,3,1]$[2,3,1]$ is NOT an almost perfect permutation (|𝑝2−𝑝−12|=|3−1|=2$|p_2-p_2^{-1}|=|3-1|=2$).
• [3,1,2]$[3,1,2]$ is NOT an almost perfect permutation (|𝑝2−𝑝−12|=|1−3|=2$|p_2-p_2^{-1}|=|1-3|=2$).
• [3,2,1]$[3,2,1]$ is an almost perfect permutation.

So we get 4$4$ almost perfect permutations.