mod = 998244353

r = [0, 1, 1]
e = [0, 1, 3]

for i in range(300000):
	r.append((r[-1] + r[-2]) % mod)
	e.append((e[-1] + e[-2]) % mod)

q = int(input())
for _ in range(q):
	n = int(input())
	print((5 * r[n] * r[n] - e[n] * e[n]) % mod)