$dp = [0,0,0,1]
Q = gets.to_i
N = $<.map &:to_i

(4...4912).each{|i|
  $dp[i] = (1..4).map{|j| $dp[i - j]}.sum % 17
}
N.each{|n|
  p $dp[(n-1) % 4912]
}