q = int(input())
n = [int(input()) for i in range(q)]

t = [0]*1000001
t[4] = 1
for i in range(5,1000001):
    t[i] = t[i-1] + t[i-2] + t[i-3] + t[i-4]
    t[i] %= 17

for i in range(q):
    print(t[n[i]])