MOD = 998244353
Q = int(input())
N = list(map(int, input().split()))

R = [1, 1]
E = [1, 3]
for i in range(2, max(N)+1):
    R.append((R[i-1] + R[i-2]) % MOD)
    E.append((E[i-1] + E[i-2]) % MOD)

for n in N:
    result = (5 * R[n]**2 - E[n]**2) 
    print(abs(result))
    print(result % MOD)