{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
import           Control.Monad               (when)
import           Control.Monad.ST            (ST, runST)
import qualified Data.Sequence               as S
import qualified Data.Vector.Unboxed.Mutable as VM

main :: IO ()
main = do
  k <- readLn
  print $ solve k

solve :: Int -> Int
solve k = runST $ do
  vs <- VM.replicate k False
  whileLeft (S.singleton (1, 1)) $ \q -> do
    let (n, d) S.:< q' = S.viewl q
    v <- VM.read vs n
    VM.write vs n True
    if | n == 0    -> return $ Right d
       | v         -> return $ Left q'
       | otherwise -> return $ Left $ (((n * 10) `mod` k, d) S.<| q') S.|> ((n + 1) `mod` k, d + 1)

whileLeft :: Monad m => a -> (a -> m (Either a b)) -> m b
whileLeft x f = f x >>= \case
  Left l  -> whileLeft l f
  Right r -> return r
