md = 998244353
r = [1, 1]
e = [1, 3]
for i in range(200000):
	r.append((r[-1] + r[-2]) % md)
	e.append((e[-1] + e[-2]) % md)
	
ans = [(5 * r[i] * r[i] - e[i] * e[i]) % md for i in range(len(r))]

for _ in range(int(input())):
	ni = int(input()) - 1
	print(ans[ni])