{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import qualified Data.IntSet as S
import           Data.Maybe  (fromJust)


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

solve :: Int -> Int
solve n = bfs 0 S.empty $ S.singleton n

bfs :: Int -> S.IntSet -> S.IntSet -> Int
bfs c s t
  | S.member 0 t = c
  | otherwise    = bfs (c + 1) s' t' where
      s' = S.union s t'
      t' = S.unions $ S.foldr' f [] t
      f x xs = S.fromList [y | y <- [ x - lookupLE x m6
                                    , x - lookupLE x m9]
                             , S.notMember y s] : xs

ms :: Int -> S.IntSet
ms m = S.fromList . takeWhile (< 100000) $ iterate (* m) 1

m6 :: S.IntSet
m6 = ms 6

m9 :: S.IntSet
m9 = ms 9

lookupLE :: Int -> S.IntSet -> Int
lookupLE x = fromJust . S.lookupLE x
