import Data.List
import Data.Int
import Control.Monad
import Control.Applicative
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

data Vector a = RVector [a] | CVector [a] deriving Show
newtype Matrix a = Matrix {getMatrix :: [[a]]} deriving Show

{-# INLINE mmap #-}
mmap f (Matrix a) = Matrix $ map (map f) a

{-# INLINE (|*|) #-}
(|*|) :: Num a => Matrix a -> Matrix a -> Matrix a
(|*|) (Matrix a) (Matrix b) = Matrix $ map (\va -> map (\vb -> sum $ zipWith (*) va vb) (transpose b)) a

{-# INLINE (|^:) #-}
(|^:) :: (Integral a , Integral b) => Matrix a -> (b, a) -> Matrix a
(|^:) (Matrix a) (0,_) = unitMatrix $ length a
(|^:) mat (1,_) = mat
(|^:) mat (p,m) = mmap (`mod` m) (if even p then t |*| t else t |*| t |*| mat)
  where t = mat |^: (div p 2, m)

{-# INLINE unitMatrix #-}
unitMatrix :: Num a => Int -> Matrix a
unitMatrix n = Matrix $ [[if i==j then 1 else 0 | j<-[1..n]] | i<-[1..n]]

{-# INLINE (|*!) #-}
(|*!) :: Num a => Matrix a -> Vector a -> Vector a
(|*!) (Matrix a) (CVector v) = CVector $ map (\r -> sum $ zipWith (*) r v) a

tetranacci 1 = 0
tetranacci 2 = 0
tetranacci 3 = 0
tetranacci 4 = 1
tetranacci n = let (CVector [x,_,_,_]) = (Matrix [[1,1,1,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]]) |^: (n-4,17) |*! (CVector [1,0,0,0]) in x

main = do
  q <- readLn :: IO Int

  mapM_ print =<< do
    map (tetranacci . fromIntegral . fst . fromJust . BS.readInteger) . BS.lines <$> BS.getContents :: IO [Int64]