Fibonacci Sequence:

• f_0=1
• f_1=1
• $fi=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