## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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\le i\le n$, it holds that $|{p}_{i}-{p}_{i}^{-1}|\le 1$, where ${p}^{-1}$ is the inverse permutation of $p$ (i.e. ${p}_{{k}_{1}}^{-1}={k}_{2}$ if and only if ${p}_{{k}_{2}}={k}_{1}$).

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

Input

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

Solution Click Below:-  👉
👇👇👇👇👇

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$.

Note

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

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

• $\left[1,2,3\right]$ is an almost perfect permutation.
• $\left[1,3,2\right]$ is an almost perfect permutation.
• $\left[2,1,3\right]$ is an almost perfect permutation.
• $\left[2,3,1\right]$ is NOT an almost perfect permutation ($|{p}_{2}-{p}_{2}^{-1}|=|3-1|=2$).
• $\left[3,1,2\right]$ is NOT an almost perfect permutation ($|{p}_{2}-{p}_{2}^{-1}|=|1-3|=2$).
• $\left[3,2,1\right]$ is an almost perfect permutation.

So we get $4$ almost perfect permutations.