import Data.Array
import Control.Monad

main = do
  q <- readLn :: IO Int

  let t = array (1,10^6) $ (1,0):(2,0):(3,0):(4,1):[(i,(t!(i-1)+t!(i-2)+t!(i-3)+t!(i-4))`mod`17) | i<-[5..10^6]] :: Array Int Int

  replicateM_ q $ do
    n <- readLn :: IO Int
    print $ t!n