{-# LANGUAGE ViewPatterns #-}

import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.Map.Strict as M
import qualified Data.Sequence as Q
import Data.List
import Data.Maybe
import Debug.Trace

traceQ :: (Show a) => String -> a -> a
-- traceQ label a = trace (label ++ ": " ++ show a) a
traceQ _ a = a

bsReadInts :: B.ByteString -> [Int]
bsReadInts = map (fst . fromJust . B.readInt) . B.words

num_digits :: Int -> Int -> Int
num_digits k n = ceiling (logBase (fromIntegral k) ((fromIntegral n) + 0.5))

power_int :: Int -> Int -> Int
power_int x y = round ((fromIntegral x) ** (fromIntegral y))

nextPower :: Int -> Int
nextPower n = 10 `power_int` (num_digits 10 n)

sumColumns :: Int -> Int
sumColumns n | n < 10    = n
sumColumns n | otherwise = (n `mod` 10) + sumColumns (n `div` 10)
  
type Stt = (Int, Int)  -- (carried, lowValue)

solve :: Int -> Int
solve valK = 
  f M.empty valK (Q.fromList [(0,0)])
  where
    f :: M.Map Int Int -> Int -> Q.Seq (Int, Int) -> Int
    f _       a (Q.viewl -> Q.EmptyL)     = a
    f rmap val (Q.viewl -> (carried, low) Q.:< queue) =
      if low_is_small then f updMap newVal newQueue
                      else f rmap   val    queue
      where
        low_is_small  = low + 1 < val &&
                        case M.lookup carried rmap of
                        Nothing     -> True
                        Just recLow -> low < recLow
        updMap = M.insert carried low rmap
        newVal = let v = (sumColumns carried) + low
                 in if v == 0 then val else min v val
        children = map csub [0..9]
        csub k = let x = k * valK + carried
                 in (x `div` 10, (x `rem` 10) + low)
        newQueue = queue Q.>< Q.fromList children

main :: IO ()
main = do
  conts <- B.getContents
  let [valK] = bsReadInts conts
      x = solve valK
  putStrLn $ show x
  
