import Data.List as List
import Data.Maybe
import Data.Map as Map
import Control.Monad.State
import Control.Applicative
import Debug.Trace

n = 100000

type Money = Int
type Times = Int

dp :: Money -> Times
dp m = evalState (f 1) $ fromList [(0,0)]
  where
  f :: Int -> State (Map.Map Money Times) Times
  f i = do
    t <- get
    let u = 1 + (minimum $ catMaybes $ List.map (\j -> Map.lookup (i - j) t) ms)
    modify $ Map.insert i u
    if m == i then return u else f $ succ i
    where
      ms = sort $ [1] ++ (takeWhile (n >) [6 ^ i | i <- [1..]]) ++ (takeWhile (n >) [9 ^ i | i <- [1..]])

main = do
  i <- read <$> getLine :: IO Int
  print $ dp i
