import Data.List (sort, delete)
import Control.Monad (guard, liftM, forM_)
import Text.Printf

f :: String -> String
f xs
  | xs == reverse (sort xs) =
      let y = minimum [x | x <- xs, x /= '0']
      in y : '0' : sort (delete y xs)
  | otherwise =
      head $ do
        let l = length xs
        i<-[l-1,l-2..0]
        let (y:ys) = drop i xs
            zs = filter (y<) ys
        guard $ not (null zs)
        let w = minimum zs
        return $ take i xs ++ [w] ++ sort (y : delete w ys)

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