#!/usr/bin/env python3
t = [ -1, 0, 0, 0, 1, ]
for i in range(5, 10 ** 6 + 100):
    t += [ sum(t[-4 :]) % 17 ]
for _ in range(int(input())):
    n = int(input())
    print(t[n])