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}$$$.