Q=int(input())

mod=998244353
R=[1 for _ in range(int(2e5)+1)]
E=[1 for _ in range(int(2e5)+1)]
E[2]=3

for i in range(3,int(2e5)+1):
    R[i]=(R[i-1]+R[i-2])%mod
    E[i]=(E[i-1]+E[i-2])%mod

for _ in range(Q):
    N=int(input())
    ans=5*R[N]**2-E[N]**2
    ans+=mod
    ans%=mod
    print(ans)