import Data.Array.IO
import Control.Monad

main = do
  q <- readLn :: IO Int

  dp <- newArray (1, 1000000) 0 :: IO (IOUArray Int Int)
  writeArray dp 4 1

  forM_ [5..1000000] $ \i ->
    sum <$> sequence [readArray dp (i - k) | k <- [1..4]]
    >>= return . flip mod 17
    >>= writeArray dp i

  forM_ [1..q] $ \i -> do
    n <- readLn :: IO Int
    readArray dp n >>= print