v=[1,-1,2,-2,4,-4,8,-8]
d=[1,2,-1,-2]
A=[[[0]*8 for i in range(8)] for k in range(70)]
mod=998244353
for i in range(8):
  x=v[i]
  for j in range(4):
    y=x*d[j]
    if abs(y)>8:
      continue
    if y==8:
      pos=0
    else:
      for k in range(8):
        if y==v[k]:
          pos=k
    A[0][i][pos]+=1
for k in range(1,70):
  for i in range(8):
    for j in range(8):
      for w in range(8):
        A[k][i][j]+=A[k-1][i][w]*A[k-1][w][j]
        A[k][i][j]%=mod
Q=int(input())
for _ in range(Q):
  N=int(input())
  v=[0]*8
  v[0]=1
  for k in range(70):
    if (N>>k)&1:
      v2=[0]*8
      for i in range(8):
        for j in range(8):
          v2[j]+=v[i]*A[k][i][j]
          v2[j]%=mod
      v=v2[:]
  result=v[0]-pow(2,N-1,mod)
  result%=mod
  print(result)