# [Solution] Almost Perfect solution codeforces

Almost Perfect solution codeforces – A permutation 𝑝p of length 𝑛n is called almost perfect if for all integer 1𝑖𝑛1≤i≤n, it holds that |𝑝𝑖𝑝1𝑖|1|pi−pi−1|≤1, where 𝑝1p−1 is the inverse permutation of 𝑝p (i.e. 𝑝1𝑘1=𝑘2pk1−1=k2 if and only if 𝑝𝑘2=𝑘1pk2=k1).

## [Solution] Almost Perfect solution codeforces

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

Input

The first line contains a single integer 𝑡t (1𝑡10001≤t≤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𝑛31051≤n≤3⋅105) — the length of the permutation.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 31053⋅105.

Output

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

## [Solution] Almost Perfect solution codeforces

input

Copy
3
2
3
50
output

Copy
2
4
830690567


## [Solution] Almost Perfect solution codeforces

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

For 𝑛=3n=3, there are only 66 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|=|31|=2|p2−p2−1|=|3−1|=2).
• [3,1,2][3,1,2] is NOT an almost perfect permutation (|𝑝2𝑝12|=|13|=2|p2−p2−1|=|1−3|=2).
• [3,2,1][3,2,1] is an almost perfect permutation.

So we get 44 almost perfect permutations.

3