R = [1, 1]
E = [1, 3]
MOD = 998244353

for _ in range(200_000):
	R.append(R[-1] + R[-2])
	R[-1] %= MOD
	E.append(E[-1] + E[-2])
	E[-1] %= MOD

Q = int(input())

for _ in range(Q):
	N = int(input()) - 1
	ans = (MOD + 5 * (R[N] ** 2 % MOD) - (E[N] ** 2 % MOD)) % MOD
	print(ans)