#P5136. sequence

sequence

题目背景

Wolfycz很喜欢数列(雾

题目描述

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

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

输入格式

第一行读入TT,表示有TT组数据

之后每一行一个整数nn

输出格式

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

5
1
9
20
50
100
2
77
15127
192911239
996781931

提示

对于5%5\%的数据,n20n\leqslant 20

对于40%40\%的数据,T5×104T\leqslant 5×10^4

对于100%100\%的数据,T105,n1018T\leqslant 10^5,n\leqslant 10^{18}