import Control.Monad
import Data.Array
import Data.List
import Text.Printf

f :: Int -> Int
f n = sum' [table ! n ! len | len <-[1..n-1]]

table :: Array Int (Array Int Int)
table = array (2,500) [(n, h n) | n <- [2..500]]
  where
    h n = array (1,n-1) [(len, g n len) | len <- [1..n-1]]

g :: Int -> Int -> Int
g _ 1 = 1
g n len = sum' $ do
  let n' = len
  len' <- [1..len-1]
  return $ (table ! n' ! len') `mul'` (table2 ! (n-n'-1, len-len'-1))

comb :: Integer -> Integer -> Integer
comb m n = product [m,m-1..m-n+1] `div` product [1..n]

table2 :: Array (Int,Int) Int
table2 = array ((0,0),(500,500)) $ do
  m<-[0..500]
  n<-[0..500]
  return ((m,n), fromInteger $ comb (toInteger m) (toInteger n) `mod` modval)

modval :: Integral a => a
modval = 100003

add', mul' :: Int -> Int -> Int
add' x y = (x + y) `mod` modval
mul' x y = fromInteger $ (toInteger x * toInteger y) `mod` modval

sum' :: [Int] -> Int
sum' = foldl' add' 0

main :: IO ()
main = do
  t <- readLn
  forM_ [(1::Int)..t] $ \x -> do
    n <- readLn
    printf "Case #%d: %d\n" x (f n)