
import qualified Data.Vector.Unboxed as V
--import Data.Array.IArray (listArray, accumArray, (!))
import Data.Array (Array, listArray, (!))
import Data.Array.MArray
import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.List (sortOn, sortBy, unfoldr, partition)
import Data.Char (isSpace)
import Control.Monad (forM_)
import Control.Monad.ST (ST, runST)
import Control.Monad.Trans.State (StateT(..))
import qualified Control.Monad.Cont as C
import qualified Data.ByteString.Char8 as B

import Debug.Trace (trace)

-- utility functions

--tr x = trace (show x) x
tr = id

--   Input functions
readInt = B.readInt . B.dropWhile isSpace

readInts :: Int -> B.ByteString -> [Int]
readInts n = take n . unfoldr readInt

readIntsV :: Int -> B.ByteString -> V.Vector Int
readIntsV n = V.unfoldrN n readInt

--readIntsA :: Int -> B.ByteString -> UArray Int Int
--readIntsA n bs = runSTUArray $ do
--  arr <- newArray_ (0,n-1)
--  go arr 0 bs
--  return arr
--  where
--    go :: STUArray s Int Int -> Int -> B.ByteString -> ST s ()
--    go arr i bs
--      | i==n = return ()
--      | otherwise = do
--        let Just (x,bs') = readInt bs
--        writeArray arr i x
--        go arr (i+1) bs'

readTsV :: Int -> B.ByteString -> V.Vector (Int,Int)
readTsV n = V.unfoldrN n $ runStateT ((,) <$> StateT readInt <*> StateT readInt)

readTs :: Int -> B.ByteString -> [(Int,Int)]
readTs n = take n . unfoldr readT where
  readT = runStateT ((,) <$> StateT readInt <*> StateT readInt)

-- main

amount = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]

solv n = runST $ do
  dp <- newArray_ (0,n) :: ST s (STUArray s Int Int)
  forM_ [0..n] $ go dp
  readArray dp n
  where
  go dp 0 = writeArray dp 0 0
  go dp i = do
    m <- minimum <$> sequence [readArray dp j|a<-amount, let j=i-a, j>=0]
    writeArray dp i (m+1)

main = do
  n <- read <$> getLine
  print $ solv n
