这是该问题的困难版。两个版本的区别在于：此版本中 $n \leq 2 \times 10^7$，且所有测试用例的 $n$ 之和不超过 $10^8$。只有解决了该问题的所有版本，你才能进行 Hack。

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

1. 从 $r$ 中同时删除所有的 10 子串†；
2. 重复上述操作，直到 $r$ 中不再存在 10 子串。

例如，$f(\texttt{100110001}) = \texttt{001}$，因为 $r$ 的变化过程如下： $\texttt{1}\underline{\texttt{10}}\texttt{0}\underline{\texttt{10}}\texttt{001} \to \texttt{0}\underline{\texttt{10}}\texttt{01} \to \texttt{001}$。

我们称一个二进制字符串 $s$ 是**“几乎回文”**，当且仅当 $f(s) = f(\operatorname{rev}(s))$‡。

Aquawave 给了你一个整数 $n$。你需要帮助他计算长度为 $n$ 的不同的“几乎回文”二进制字符串的数量，结果对 $998244353$ 取模。

∗ 二进制字符串是指每个字符都是 0 或 1 的字符串。

† 字符串 $a$ 是字符串 $b$ 的子串，如果 $a$ 可以通过删除 $b$ 的开头若干个（可能为零个或全部）字符以及结尾若干个（可能为零个或全部）字符得到。

‡ $\operatorname{rev}(s)$ 是将 $s$ 从右向左书写得到的字符串。例如，$\operatorname{rev}(\texttt{10100}) = \texttt{00101}$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。

接下来每个测试用例的描述占一行，每行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^7$）—— 二进制字符串的长度。

保证所有测试用例的 $n$ 之和不超过 $10^8$。

输出

对于每个测试用例，输出一个整数 —— 长度为 $n$ 的不同的“几乎回文”二进制字符串的数量，对 $998244353$ 取模。

示例

输入：

12
1
2
3
4
5
6
7
8
9
10
100
1024

输出：

2
2
4
8
12
26
44
86
164
302
307217648
950903700

提示

• 在第一个测试用例中，所有长度为 $1$ 的二进制字符串都是“几乎回文”。
• 在第二个测试用例中，所有长度为 $2$ 的“几乎回文”二进制字符串是 $\texttt{00}$ 和 $\texttt{11}$。
• 在第三个测试用例中，所有长度为 $3$ 的“几乎回文”二进制字符串是 $\texttt{000}$、$\texttt{010}$、$\texttt{101}$ 和 $\texttt{111}$。