import Control.Monad
import qualified Data.Set as Set
import qualified Data.Map as Map
import Text.Printf

f :: String -> Integer
f s@(c:cs) = sum [ x * base ^ i | (x,i) <- zip xs [l-1, l-2 ..] ]
  where
    base = fromIntegral $ max 2 (Set.size $ Set.fromList s)
    xs = 1 : g (Map.singleton c 1) (0 : [2..base-1]) cs
    l = length s

g :: Map.Map Char Integer -> [Integer] -> String -> [Integer]
g m ds [] = []
g m ds (c:cs)
  = case Map.lookup c m of
      Just d -> d : g m ds cs
      Nothing ->
        case ds of
          (d:ds) -> d : g (Map.insert c d m) ds cs

main :: IO ()
main = do
  t <- liftM read getLine
  forM_ [(1::Int)..t] $ \i -> do
     s <- getLine
     printf "Case #%d: %d\n" i (f s)