E. Почти идеально
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка $$$p$$$ длины $$$n$$$ называется почти идеальной, если для всех целых $$$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$$$.

Пример
Входные данные
3
2
3
50
Выходные данные
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$$$ почти идеальные перестановки.