This is the hard version of the problem. The difference between the versions is that in this version, $$$n\le 2\cdot 10^7$$$, and the sum of $$$n$$$ over all test cases does not exceed $$$10^8$$$. 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:

Delete all $$$\texttt{10}$$$ substrings$$$^{\text{†}}$$$ simultaneously from $$$r$$$;
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 2\cdot 10^7$$$) — the length of the binary strings.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^8$$$.

Output

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

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

Beyond the Palindrome (Hard Version)

Examples