MOD = 998244353

mx = 2*10**5 + 10
R = [0]*mx
E = [0]*mx
R[1],R[2] = 1,1
E[1],E[2] = 1,3
for i in range(3,mx):
    R[i] = R[i-1] + R[i-2]
    R[i] %= MOD
    E[i] = E[i-1] + E[i-2]
    E[i] %= MOD

Q = int(input())
for _ in range(Q):
    N = int(input())
    R2 = R[N]*R[N]%MOD
    E2 = E[N]*E[N]%MOD
    ans = (5*R2%MOD - E2)%MOD
    print(ans)