E1. За пределами палиндрома (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n\le 10^6$$$, и сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Для бинарной строки$$$^{\text{∗}}$$$ $$$r$$$ определим $$$f(r)$$$ как результат следующего процесса:

  1. Удалите все подстроки $$$\texttt{10}$$$$$$^{\text{†}}$$$ одновременно из $$$r$$$;
  2. Повторяйте вышеуказанную операцию, пока в $$$r$$$ есть подстроки $$$\texttt{10}$$$.

Например, $$$f(\mathtt{100110001})=\mathtt{001}$$$, потому что $$$r$$$ изменяется следующим образом: $$$\mathtt{\underline{10}01\underline{10}001}\to \mathtt{0\underline{10}01}\to\mathtt{001}$$$.

Мы называем бинарную строку $$$s$$$ почти-палиндромом, если и только если $$$f(s)=f(\mathrm{rev}(s))$$$$$$^{\text{‡}}$$$.

Аквавейв дал вам целое число $$$n$$$. Вам нужно помочь ему найти количество различных почти-палиндромных бинарных строк длины $$$n$$$, по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ является либо $$$\texttt{0}$$$, либо $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов с начала и нескольких (возможно, ни одного или всех) символов с конца.

$$$^{\text{‡}}$$$$$$\mathrm{rev}(s)$$$ — это строка, полученная путем записи $$$s$$$ справа налево. Например, $$$\mathrm{rev(\mathtt{10100})=\mathtt{00101}}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 10^6$$$) — длина бинарных строк.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных почти-палиндромных бинарных строк длины $$$n$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
12
1
2
3
4
5
6
7
8
9
10
100
1024
Выходные данные
2
2
4
8
12
26
44
86
164
302
307217648
950903700
Примечание

В первом наборе входных данных все бинарные строки длины $$$1$$$ являются почти-палиндромами.

Во втором наборе входных данных все почти-палиндромные бинарные строки длины $$$2$$$ — это $$$\mathtt{00}$$$ и $$$\mathtt{11}$$$.

В третьем наборе входных данных все почти-палиндромные бинарные строки длины $$$3$$$ — это $$$\mathtt{000}$$$, $$$\mathtt{010}$$$, $$$\mathtt{101}$$$ и $$$\mathtt{111}$$$.