T=int(input()) for _ in range(T): n=int(input()) M=998244353 def seki(a,b): l=len(a) c=[[0]*l for i in range(l)] for i in range(l): for j in range(l): for k in range(l): c[i][j]+=a[i][k]*b[k][j] c[i][j]%=M return c A=[ [1,1,0,0,0,0,1,0], [1,1,0,0,0,0,1,0], [1,1,1,1,0,0,1,0], [1,1,1,1,0,0,1,0], [0,0,1,1,1,1,0,0], [0,0,1,1,1,1,0,0], [0,0,0,0,1,1,0,1], [0,0,0,0,1,1,0,1], ] l=len(A) B=[[0]*l for i in range(l)] for i in range(l): B[i][i]=1 for i in range(61): if (n>>i)&1: B=seki(A,B) A=seki(A,A) ans=B[0][0]+B[-1][0] ans-=pow(2,n,M)*pow(2,M-2,M) ans%=M print(ans)