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 (10) substrings(^{\text{†}}) simultaneously from (r); Repeat the above operation until there are no (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 (0) or (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 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). For each test case, output a single integer — the number of dist