题目翻译

E. 几乎完美排列
每个测试的时间限制：$3$ 秒
内存限制：$256$ MB

一个长度为 $n$ 的排列 $p$ 被称为几乎完美的，如果对于所有整数 $1 \le i \le n$，都有 $|p_i - p^{-1}_i| \le 1$，其中 $p^{-1}$ 是 $p$ 的逆排列（即 $p^{-1}_{k_1} = k_2$ 当且仅当 $p_{k_2} = k_1$）。

请统计长度为 $n$ 的几乎完美排列的数量，结果对 $998244353$ 取模。

输入

第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。
接下来 $t$ 行，每行一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）——排列的长度。
保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出

对于每个测试用例，输出一行一个整数——长度为 $n$ 的几乎完美排列的数量对 $998244353$ 取模的结果。

样例

输入：

3
2
3
50

输出：

2
4
830690567

样例解释
对于 $n=2$，两个排列 $[1,2]$ 和 $[2,1]$ 都是几乎完美的。
对于 $n=3$，总共有 $6$ 个排列，逐一检查后得到 $4$ 个几乎完美的排列：
$[1,2,3]$，$[1,3,2]$，$[2,1,3]$，$[3,2,1]$。