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