for _ in range(int(input())):
	print([998244349,4][int(input())%2])