MOD = 998244353
r = [0, 1]
e = [2, 1]
for i in range(1, 2 * 10 ** 5 + 1):
    r.append((r[-1] + r[-2]) % MOD)
    e.append((e[-1] + e[-2]) % MOD)

Q = int(input())
for _ in range(Q):
    n = int(input())
    print((5 * r[n] ** 2 - e[n] ** 2) % MOD)