import Data.Array.IO
import Control.Monad

main = do
  q <- readLn :: IO Int

  dp <- newArray (0, 4911) 0 :: IO (IOUArray Int Int)
  writeArray dp 3 1

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

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