{-# LANGUAGE ImplicitParams #-}

main = do
  content <- getContents
  let hd:tl = lines content
  let ?totalcases = read hd
  process 1 $ map (map read) (map words tl)
          
newtype Int1000 = Int1000 Int deriving Eq
instance Num Int1000 where
  (Int1000 a) + (Int1000 b) = Int1000 ((a+b) `mod` 1000)
  (Int1000 a) - (Int1000 b) = Int1000 ((a-b) `mod` 1000)
  (Int1000 a) * (Int1000 b) = Int1000 ((a*b) `mod` 1000)
  fromInteger n = Int1000 ((fromInteger n) `mod` 1000)
instance Show Int1000 where
  show (Int1000 a) = tail (show (1000+a))

ab :: Int -> Int1000
ab 0 = 2
ab 1 = 6
ab n | even n = (ab (n `div` 2))^2 - 2 * 2^n
     | odd n = (ab (n `div` 2)) * (ab ((n `div` 2) + 1)) - 3 * 2^n

-- main = interact $ unlines . zipWith (++) [ "Case #" ++ show caseno ++ ": " | caseno <- [1..] ] . map (show . (+ (-1)) . ab . read) . tail . lines

process :: (?totalcases :: Int) -> Int -> [[Int]] -> IO ()
process count content = do
  if count > ?totalcases then return ()
    else case content of
         ([n]:tl) ->
             do
               putStr ("Case #" ++ show count ++ ": ")
               putStrLn $ show (ab n - 1)
               process (count+1) tl