Description

This problem is as follows:

There is an electric field formed by $n$ point charges. Assume each point charge produces a uniform electric field rather than a point-charge field, and the $i$-th point charge has field strength $E_i=i$.

Now place a negatively charged test charge in this field. As soon as the test charge touches any point charge, it will "fuse" with that point charge and release a huge amount of energy.

Because the field strengths produced by the point charges differ, the test charge is attracted to each point charge with different force; the stronger the attraction a point charge exerts on the test charge, the greater the probability of being drawn to that point charge, and the probability is proportional to the attraction.

Assume the smallest point charge exerts attraction $F$ on the test charge. Then another point charge exerts $iF$. Suppose the probability of touching the smallest point charge is $P$. Then the probability for each point is $iP$. After touching a point charge, the released energy is $\mathrm{Fib}(E_i)$.

Find the expected released energy.

The good news is that as long as she gets points on this problem, Satania will pass!

Input Format

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains an integer $n$, the number of point charges.

Output Format

For each query, output one integer representing the expected energy. To avoid precision issues, please output the answer modulo $998{,}244{,}353$.

1
2

1

Hint

• Sample Explanation

$\dfrac{1}{3}\times \mathrm{Fib}(1)+\dfrac{2}{3}\times \mathrm{Fib}(2)=1$.

Please read the problem carefully along with the sample.

• Constraints

• For $10\%$ of the testdata, $T=1$, $n=2$.

• For $30\%$ of the testdata, $T \le 10$, $1 \le n \le 10^6$.

• For $60\%$ of the testdata, $T \le 10^6$, $1 \le n \le 10^6$.

• For $100\%$ of the testdata, $T \le 10^6$, $1 \le n \le 10^9$, and it is guaranteed that $n \ne 998244352$ and $n \ne 998244353$.

$\mathrm{Fib}(i)$ is the Fibonacci sequence.

$$\mathrm{Fib}(i)=\begin{cases} 1 & i\le 2 \cr \mathrm{Fib}(i-1)+\mathrm{Fib}(i-2) & i > 2 \end{cases}$$

Translated by ChatGPT 5