P5136 sequence

Wolfycz really likes sequences (just kidding).

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.

The first line contains $T$, meaning there are $T$ test cases. Then each following line contains one integer $n$.

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.

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