mod = 998244353; r = [1,1]; e = [1,3]
for i in range(2*10**5-1): r.append((r[-2]+r[-1])%mod); e.append((e[-2]+e[-1])%mod)
for _ in range(int(input())): n = int(input())-1; print((5*r[n]**2-e[n]**2)%mod)