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