mod = 998244353
R = [1,1]
E = [1,3]
for _ in range(2*10**5):
    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-1]**2-E[N-1]**2)%mod)