长度为 $$$n$$$ 的排列 $$$p$$$ 被称为近乎完美,如果对于所有整数 $$$1 \leq i \leq n$$$,它保持 $$$\lvert p_i - p^{-1}_i \rvert \le 1$$$,其中 $$$p^{-1}$$$ 是 $$$p$$$ 的逆排列(即 $$$p^{-1}_{k_1} = k_2$$$ 当且仅当 $$$p_{k_2} = k_1$$$)。
计算长度 $$$n$$$ 模 $$$998244353$$$ 的近乎完美排列的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。每个测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 排列的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 长度 $$$n$$$ 模 $$$998244353$$$ 的几乎完美排列的数量。
示例
输入 #1
3 2 3 50
输出 #1
2 4 830690567
注意
对于 $$$n = 2$$$,两种排列 $$$[1, 2]$$$ 和 $$$[2, 1]$$$ 几乎是完美的。
对于 $$$n = 3$$$,只有 $$$6$$$ 排列。看看所有这些,我们可以得到:
- $$$[1, 2, 3]$$$ 是一个近乎完美的排列。
- $$$[1, 3, 2]$$$ 是一个近乎完美的排列。
- $$$[2, 1, 3]$$$ 是一个近乎完美的排列。
- $$$[2, 3, 1]$$$ 不是一个几乎完美的排列($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$$$)。
- $$$[3, 1, 2]$$$ 不是一个几乎完美的排列($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$$$)。
- $$$[3, 2, 1]$$$ 是一个近乎完美的排列。
所以我们得到 $$$4$$$ 几乎完美的排列。