mod=998244353

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

for i in range(2*10**5):
    R.append((R[-1]+R[-2])%mod)
    E.append((E[-1]+E[-2])%mod)

Q=int(input())
for tests in range(Q):
    x=int(input())
    print((5*R[x]**2 - E[x]**2)%mod)