import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Q,*N = map(int,read().split())

P = 4912

U = 10000
T = [0,0,0,0,1] + [0] * U
for n in range(5,U):
    T[n] = sum(T[n-4:n]) % 17

answer = (T[n % P + P] for n in N)
print('\n'.join(map(str,answer)))