CF2135E1.Beyond the Palindrome (Easy Version)

这是该问题的简单版本。两个版本的区别在于，这一版本中 $n \le 10^6$，并且所有测试用例的 $n$ 之和不超过 $10^6$。仅当你解决了所有版本后才能进行 Hack。

对于一个二进制串 $r$，我们定义 $f(r)$ 为如下处理过程的结果：

1. 同时删除 $r$ 中所有的 $\texttt{10}$ 子串；
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))$，我们称其为“almost-palindrome”。

给定一个整数 $n$，请你帮 Aquawave 计算长度为 $n$ 的不同的 almost-palindrome 二进制串个数，答案对 $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$ 的不同的 almost-palindrome 二进制串个数，对 $998\,244\,353$ 取模。

在第一个测试用例中，所有长度为 $1$ 的二进制串都是 almost-palindrome。

在第二个测试用例中，所有长度为 $2$ 的 almost-palindrome 二进制串为 $\mathtt{00}$ 和 $\mathtt{11}$。

在第三个测试用例中，所有长度为 $3$ 的 almost-palindrome 二进制串为 $\mathtt{000}$，$\mathtt{010}$，$\mathtt{101}$ 和 $\mathtt{111}$。

由 ChatGPT 5 翻译