import sys
input = sys.stdin.readline

Q = int(input())
M = 2 * 10 ** 5 + 5
R, E = [1] * M, [1] * M
E[1] = 3
mod = 998244353
for i in range(2, M):
    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())
    print( (5 * R[N - 1] ** 2 - E[N - 1] ** 2) % mod )