B'A permutation p of length n is called almost perfect if for all integer 1 <= q i <= q n , it holds that lvert p_i - p^{-1}_i rvert <= 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 <= q t <= q 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 <= q n <= q 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: So we get 4 almost perfect permutations. '...