import sys
input = sys.stdin.readline
for _ in range(int(input())):
	print([998244349,4][int(input())%2])