a = []
gets.to_i.times do
  a << gets.to_i
end
def tetra(n)
  a = 0
  b = 0
  c = 0
  d = 1
  e = 0
  case n
  when 1..3
    0
  when 4
    1
  else
    (5..n).each do |i|
      e = a + b + c + d
      a, b, c, d = b, c ,d, e
    end
    e
  end
end
a.each do |i|
  p tetra(i)%17
end