{-# LANGUAGE  ViewPatterns #-}
import Data.List
import qualified Data.Set as S
import Control.Monad

main :: IO ()
main = readLn >>= print . solve 

solve :: Int -> Int 
solve k = walk S.empty $ cons (1, 1) empty
    where
        walk s (pop -> Just ((v, d), xs))
            | v == 0 = d
            | S.member i s && S.member j s = walk t xs
            | S.member i s = walk t $ snoc (j, d + 1) xs
            | S.member j s = walk t $ cons (i, d) xs
            | otherwise = walk t . cons (i, d) $ snoc (j, d + 1) xs
            where
                i = (v * 10) `mod` k 
                j = (v + 1) `mod` k
                t = S.insert v s

data DQ a = DQ [a] [a]
    deriving (Show, Eq)

empty :: DQ a
empty = DQ [] []

cons :: a -> DQ a -> DQ a
cons v (DQ xs ys) = DQ (v : xs) ys

snoc :: a -> DQ a -> DQ a
snoc v (DQ xs ys) = DQ xs $ v : ys

pop :: DQ a -> Maybe (a, DQ a)
pop (DQ (x : xs) ys) = return (x, DQ xs ys)
pop (DQ _ []) = Nothing
pop (DQ _ ys) = pop $ DQ (reverse ys) []


