a,b,c,d=0,0,0,1
rs = [1]
5000.times do |i|
  rs << a % 17
  a,b,c,d=b,c,d,(a+b+c+d)
end
gets.to_i.times{p rs[gets.to_i%4912]}