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