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