Background

Wolfycz really likes sequences (just kidding).

Problem Description

Wolfycz really enjoys studying sequences, and he also likes the golden ratio. One day, Wolfycz wrote down a sequence and defined $A_i=\lceil(\dfrac{\sqrt{5}+1}{2})^i\rceil$. However, Wolfycz does not know the value of $A_n$, so he hopes you can help him.

Note: Please pay attention to the impact of constant factors on the running time of your program.

Input Format

The first line contains $T$, meaning there are $T$ test cases.

Then each following line contains one integer $n$.

Output Format

Output $T$ lines in total. Each line contains one integer, representing the value of $\lceil(\dfrac{\sqrt{5}+1}{2})^n\rceil$. Output the answer modulo 998244353.

5
1
9
20
50
100

2
77
15127
192911239
996781931

Hint

For $5\%$ of the testdata, $n\leqslant 20$.

For $40\%$ of the testdata, $T\leqslant 5×10^4$.

For $100\%$ of the testdata, $T\leqslant 10^5,n\leqslant 10^{18}$.

Translated by ChatGPT 5