NMAX = 1e6.to_i

t = [0,0,0,1]

NMAX.times do |i|
    t.push (t[-1]+t[-2]+t[-3]+t[-4])%17
end

gets.to_i.times do
    n = gets.to_i
    p t[n-1]
end