Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

fft

math

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Almost Perfect

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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

Output

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

Example

Input

32350

Output

2 4 830690567

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/01/2024 11:47:18 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|