T=int(input())
for t in range(T):
    N=int(input())
    ans=[998244349,4][N%2]
    print(ans)