4578 B

Fibonacci Sequence:

f0= 1 (1)

f1 = 1 (2)

fi = fi-1+ fi-2, i ≥ 2 (3)

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

In particular: f0 and f1 are two different Fibonacci numbers.

For example: 7 = 5 + 2 = f4 + f2, 7 = 3 + 2 + 1 + 1 = f3+ f2 + f1 + f0 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 = f3 + f2 + f1 + f0. In this representation, the value w(F(x)) is: 3 ∗ 2 ∗ 1 ∗ 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 ≤ T ≤ 1e6).

The next T line, each line has a natural number n(1 ≤ n ≤ 1e7)