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

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

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.