import Data.List
import Data.Int
import Control.Monad

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

getVectorList (RVector a) = a
getVectorList (CVector a) = a

rtoc (RVector v) = CVector v
ctor (CVector v) = RVector v

(!+!) :: Num a => Vector a -> Vector a -> Vector a
(!+!) (RVector a) (RVector b) = RVector $ zipWith (+) a b
(!+!) (CVector a) (CVector b) = CVector $ zipWith (+) a b
(!+!) _ _ = error "no addition between a row vector and a column vector"

vneg :: Num a => Vector a -> Vector a
vneg (RVector a) = RVector $ map negate a
vneg (CVector a) = CVector $ map negate a

(!-!) a b = a !+! (vneg b)

(!.!) :: Num a => Vector a -> Vector a -> a
(!.!) a b = sum $ zipWith (*) (getVectorList a) (getVectorList b)

(!*) :: Num a => Vector a -> a -> Vector a
(!*) (RVector a) n = RVector $ map (*n) a
(!*) (CVector a) n = RVector $ map (*n) a

(*!) b a = a !* b

(!/) a b = a !* (1 / b)

vabs :: (Real a, Num a) => Vector a -> Double
vabs a = sqrt $ sum $ map (realToFrac . (^2)) (getVectorList a)

vcross :: Num a => Vector a -> Vector a -> Vector a
vcross (RVector [a1,a2,a3]) (RVector [b1,b2,b3]) = RVector $ [a2*b3-a3*b2, a3*b1-a1*b3, a1*b2-a2*b1]
vcross (CVector [a1,a2,a3]) (CVector [b1,b2,b3]) = CVector $ [a2*b3-a3*b2, a3*b1-a1*b3, a1*b2-a2*b1]
vcross _ _ = error "cross product error"

mmap f (Matrix a) = Matrix $ map (map f) a

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

(|*) :: Num a => Matrix a -> a -> Matrix a
(|*) (Matrix a) n = Matrix $ map (map (*n)) a

(*|) n a = a |* n
 
(|+|) :: Num a => Matrix a -> Matrix a -> Matrix a
(|+|) (Matrix a) (Matrix b) = Matrix $ zipWith (zipWith (+)) a b

mneg (Matrix a) = Matrix $ map (map negate) a

(|-|) a b = a |+| (mneg b)

(|^) :: (Num a, Integral b) => Matrix a -> b -> Matrix a
(|^) (Matrix a) 0 = unitMatrix $ length a
(|^) mat 1 = mat
(|^) mat p = if even p then t |*| t else t |*| t |*| mat
  where t = mat |^ (div p 2)

(|^:) :: (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)

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

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

(!*|) :: Num a => Vector a -> Matrix a -> Vector a
(!*|) (RVector v) (Matrix a) = RVector $ map (\c -> sum $ zipWith (*) v c) (transpose 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

  replicateM_ q $ do
    n <- readLn :: IO Int64

    print $ tetranacci n