def make_tetra(n)
  t = Array.new(n + 1, 0)
  t[4]= 1
  (5 .. n).each do |i|
    t[i] = (t[i - 1] + t[i - 2] + t[i - 3] + t[i - 4]) % 17
  end
  t
end

N = gets.to_i
Q = N.times.map{ gets.to_i }
T = make_tetra(Q.max)
puts Q.map{|a| T[a] }