import Control.Applicative

string2int str = read str :: Int

mtetra = (map tetra [0 ..] !!)
  where tetra 1 = 0
        tetra 2 = 0
        tetra 3 = 0
        tetra 4 = 1
        tetra n = mtetra (n-1) + mtetra (n-2) + mtetra (n-3) + mtetra (n-4)

ans n = do
  ss <- getLine
  let n = string2int ss
  print $ mod (mtetra n) 17

main :: IO ()
main = do
  ss <- getLine
  let q = string2int ss
  mapM_ ans $ enumFromTo 0 (q-1)