import Data.Sequence((|>),(<|),ViewR(..))
import qualified Data.Sequence as Sq
import Data.Map ((!))
import qualified Data.Map as M
import Data.Bool

main=readLn>>=print.solve

solve :: Int -> Int
solve k = go (M.fromList$(1,1):zip(0:[2..k-1])(repeat 100)) (Sq.fromList[1]) ! 0
  where
  go :: M.Map Int Int -> Sq.Seq Int -> M.Map Int Int
  go map seq
   | seq == Sq.empty = map
   | otherwise = go newMap newSeq
    where
    newMap = doif (M.insert p0 len) update0 $ doif (M.insert p1 (len+1)) update1 map
    newSeq = doif (|> p0) update0 $ doif (p1 <|) update1 seq'
    (update0,update1) = (eval 0 p0, eval 1 p1)
    eval d p = (len+d) < map!p
    len = map!n
    (seq' :> n) = Sq.viewr seq
    (p0,p1) = (n*10`mod`k, (n+1)`mod`k)
    doif = bool id
