mod = 998244353
R = [0, 1, 1]
for i in range(200020):
	R.append((R[-1] + R[-2]) % mod)
E = [0, 1, 3]
for i in range(200020):
	E.append((E[-1] + E[-2]) % mod)
for _ in range(int(input())):
	N = int(input())
	print((5 * R[N] * R[N] - E[N] * E[N]) % mod)