Fibonacci Sequence:

• $f_0=1$
• $f_1=1$
• $f_i=f_{i-1}+f_{i-2}, i≥2$

Fibonacci representation $F(x)$: Any natural number $x$ can be expressed as the sum of a set of different Fibonacci numbers.

In particular: $f_0$ and $f_1$ are two different Fibonacci numbers.

For example: $7=5+2=f_4+f_2, \ 7=3+2+1+1=f_3+f_2+f_1+f_0$ indicates that $7$ corresponds to at least two Fibonacci representations.

The value of the Fibonacci representation $w(F(x))$: defined as the product of the Fibonacci numbers in the representation .

For example: $7=3+2+1+1=f_3+f_2+f_1+f_0$. In this representation, the value $w(F(x))$ is: $3 \times 2 \times 1 \times 1=6$.

With the above definitions, now, find the sum of all Fibonacci representations’ value of a given number $x$.

To simplify the question, please output the answer modulo lovely $998244353$.

The first line contains a positive integer $T(1\leq T≤10^6)$.

The next $T$ line, each line has a natural number $n(1\leq n ≤10^7)$.

The output should contain $T$ lines, each line with an integer, which represents the value of the answer modulo lovely $998244353$.

$7=5+2=5+1+1=3+2+1+1$, then $5 \times 2+5 \times 1 \times 1+3 \times 2 \times 1 \times 1=21$