(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 1))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload :cl-debug-print))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro nlet (name args &body body)
  `(labels ((,name ,(mapcar #'car args) ,@body))
     (,name ,@(mapcar #'cadr args))))

;; (with-memoizing (:hash-table :test #'equal :key #'cons)
;;   (defun ...))
;; (with-memoizing (:array (10 10 10) :initial-element -1 :element-type 'fixnum)
;;   (defun ...))
(defmacro with-memoizing (cache-attribs defun-form)
  (labels ((ensure-list (thing)
             (if (atom thing) (list thing) thing)))
    (let* ((cache-attribs (ensure-list cache-attribs))
           (cache-type (first cache-attribs))
           (dimensions (and (eql cache-type :array)
                            (ensure-list (second cache-attribs))))
           (rank (length dimensions))
           (rest-attribs (ecase cache-type
                           (:hash-table (cdr cache-attribs))
                           (:array (cddr cache-attribs))))
           (key-func (prog1 (getf rest-attribs :key) (remf rest-attribs :key)))
           (cache-form (case cache-type
                         (:hash-table `(make-hash-table ,@rest-attribs))
                         (:array `(make-array ',dimensions ,@rest-attribs)))))
      (let ((cache (gensym))
	    (value (gensym))
	    (exists-p (gensym))
	    (original-func (gensym))
	    (args-lst (gensym))
            (indices (loop repeat rank collect (gensym))))
        (ecase (car defun-form)
          ((defun nlet)
           (destructuring-bind (_ name args &body body) defun-form
             (declare (ignore _))
             `(let ((,cache ,cache-form))
                (,(car defun-form) ,name ,args
                 ,(let ((args (case (car defun-form)
                                (defun args)
                                (nlet (mapcar (lambda (x) (car (ensure-list x))) args)))))
                    `(labels ((,original-func ,args ,@body))
                       (declare (inline ,original-func))
                       ,(case cache-type
                          (:hash-table
                           `(let ((,args-lst (funcall ,(or key-func #'list) ,@args)))
                              (declare (dynamic-extent ,args-lst))
                              (multiple-value-bind (,value ,exists-p)
                                  (gethash ,args-lst ,cache)
                                (if ,exists-p
                                    ,value
                                    (setf (gethash ,args-lst ,cache)
                                          (,original-func ,@args))))))
                          (:array
                           (assert (member :initial-element rest-attribs))
                           (let ((null-flag (getf rest-attribs :initial-element)))
                             (if key-func
                                 `(multiple-value-bind ,indices
                                      (funcall ,key-func ,@args)
                                    (let ((,value (aref ,cache ,@indices)))
                                      (if (eql ,null-flag ,value)
                                          (setf (aref ,cache ,@indices)
                                                (,original-func ,@args))
                                          ,value)))
                                 `(let ((,value (aref ,cache ,@args)))
                                    (if (eql ,null-flag ,value)
                                        (setf (aref ,cache ,@args)
                                              (,original-func ,@args))
                                        ,value)))))))))))))))))

(defmacro println (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))

;; Hauptteil
(defconstant +undrawable-flag+ (- (expt 2 31) 1))
(with-memoizing (:array 100001
                 :element-type '(unsigned-byte 31)
                 :initial-element +undrawable-flag+)
  (defun solve (num)
    (if (zerop num)
        0
        (min (if (< num 59049) +undrawable-flag+ (1+ (solve (- num 59049))))
             (if (< num 46656) +undrawable-flag+ (1+ (solve (- num 46656))))
             (if (< num 7776) +undrawable-flag+ (1+ (solve (- num 7776))))
             (if (< num 6561) +undrawable-flag+ (1+ (solve (- num 6561))))
             (if (< num 1296) +undrawable-flag+ (1+ (solve (- num 1296))))
             (if (< num 729) +undrawable-flag+ (1+ (solve (- num 729))))
             (if (< num 216) +undrawable-flag+ (1+ (solve (- num 216))))
             (if (< num 81) +undrawable-flag+ (1+ (solve (- num 81))))
             (if (< num 36) +undrawable-flag+ (1+ (solve (- num 36))))
             (if (< num 9) +undrawable-flag+ (1+ (solve (- num 9))))
             (if (< num 6) +undrawable-flag+ (1+ (solve (- num 6))))
             (1+ (solve (- num 1)))))))

(deftype uint nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (let* ((amount (read)))
    (println (solve amount))))

#-swank(main)


Measured memory_bytes: 17376