T = Array.new(1 << 20, 0)
T[4] = 1
(5 ... T.size).each do |i|
  T[i] = (T[i - 1] + T[i - 2] + T[i - 3] + T[i - 4]) % 17
end
N = gets.to_i
puts N.times.map{ T[gets.to_i] }