t = {0, 0, 0, 1}
matched = false
i = 5
while(not matched) do
    t[i] = (t[i -1] + t[i - 2] + t[i - 3] + t[i - 4]) % 17
    if(t[i] == 1 and t[i - 1] == 0 and t[i - 2] == 0 and t[i - 3] == 0) then
        matched = true
    end
    i = i + 1
end
mod = i - 5

n = io.read("*n")
for i = 1, n do
    a = io.read("*n")
    a = a % mod
    print(t[(a - 1) % mod + 1])
end