E1. Beyond the Palindrome (Easy Version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Input

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

Output

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

Example
Input
12
1
2
3
4
5
6
7
8
9
10
100
1024
Output
2
2
4
8
12
26
44
86
164
302
307217648
950903700
Note

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