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