R=[0]*(3*10**5)
E=[0]*(3*10**5)
mod=998244353
R[1]=1
R[2]=1
E[1]=1
E[2]=3
for i in range(3,3*10**5):
  R[i]=R[i-1]+R[i-2]
  E[i]=E[i-1]+E[i-2]
  R[i]%=mod
  E[i]%=mod
Q=int(input())
for i in range(Q):
  x=int(input())
  ans=5*R[x]**2-E[x]**2
  ans%=mod
  print(ans)