背景

Wolfycz很喜欢数列（雾

题目描述

Wolfycz非常喜欢研究数列，同时他也喜欢研究黄金分割率，有一天Wolfycz写下了一个数列，他令$A_i=\lceil(\dfrac{\sqrt{5}+1}{2})^i\rceil$，但是Wolfycz并不知道$A_n$的值，所以希望你来帮帮他

注：请注意常数因子对程序运行效率的影响

输入格式

第一行读入$T$，表示有$T$组数据

之后每一行一个整数$n$

输出格式

输出共$T$行，每行一个整数，表示$\lceil(\dfrac{\sqrt{5}+1}{2})^n\rceil$的值，答案对998244353取模

5
1
9
20
50
100

2
77
15127
192911239
996781931

提示

对于$5\%$的数据，$n\leqslant 20$

对于$40\%$的数据，$T\leqslant 5×10^4$

对于$100\%$的数据，$T\leqslant 10^5,n\leqslant 10^{18}$