import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd

mod = 998244353
rr = [1,1]
ee = [1,3]
for i in range(2*10**5+100):
    rr.append(rr[-1] + rr[-2])
    ee.append(ee[-1] + ee[-2])
    rr[-1] %= mod
    ee[-1] %= mod

q = int(input())
for i in range(q):
    n = int(input())
    print((5*rr[n-1]**2 - ee[n-1]**2)%mod)