M=998244353
N=200000
R=[None,1,1]
E=[None,1,3]
D=[None]
for r,e in zip(R[1:],E[1:]):
	d=(5*r*r-e*e)%M
	if d<0:
		d+=M
	D.append(d)
	
	
for i in range(3,N+1):
	R.append((R[-1]+R[-2])%M)
	E.append((E[-1]+E[-2])%M)
	d=(5*R[i]*R[i]-E[i]*E[i])%M
	if d<0:
		d+=M
	D.append(d)

Q=int(input())
for _ in range(Q):
	n=int(input())
	print(D[n])