CF2135E1 Beyond the Palindrome (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $$$n\le 10^6$$$, and the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$. You can hack only if you solved all versions of this problem. For a binary string$$$^{\text{∗}}$$$ $$$r$$$, we define $$$f(r)$$$ as the result of the following process: 1. Delete all $$$\texttt{10}$$$ substrings$$$^{\text{†}}$$$ simultaneously from $$$r$$$; 2. Repeat the above operation until there are no $$$\texttt{10}$$$ substrings in $$$r$$$. For example, $$$f(\mathtt{100110001})=\mathtt{001}$$$ because $$$r$$$ changes as follows: $$$\mathtt{\underline{10}01\underline{10}001}\to \mathtt{0\underline{10}01}\to\mathtt{001}$$$. We call a binary string $$$s$$$ almost-palindrome if and only if $$$f(s)=f(\mathrm{rev}(s))$$$ $$$^{\text{‡}}$$$. Aquawave has given you an integer $$$n$$$. You have to help him find the number of distinct almost-palindrome binary strings of length $$$n$$$, modulo $$$998\,244\,353$$$. $$$^{\text{∗}}$$$A binary string is a string where each character is either $$$\texttt{0}$$$ or $$$\texttt{1}$$$. $$$^{\text{†}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. $$$^{\text{‡}}$$$ $$$\mathrm{rev}(s)$$$ is the string obtained by writing $$$s$$$ from right to left. For example, $$$\mathrm{rev(\mathtt{10100})=\mathtt{00101}}$$$.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The only line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 10^6$$$) — the length of the binary strings. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

For each test case, output a single integer — the number of distinct almost-palindrome binary strings of length $$$n$$$, modulo $$$998\,244\,353$$$.

In the first test case, all binary strings of length $$$1$$$ are almost-palindrome. In the second test case, all almost-palindrome binary strings of length $$$2$$$ are $$$\mathtt{00}$$$ and $$$\mathtt{11}$$$. In the third test case, all almost-palindrome binary strings of length $$$3$$$ are $$$\mathtt{000}$$$, $$$\mathtt{010}$$$, $$$\mathtt{101}$$$, and $$$\mathtt{111}$$$.