(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
;; (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 7) 1))
(with-memoizing (:array 100001
                 :element-type '(unsigned-byte 7)
                 :initial-element +undrawable-flag+)
  (defun solve (num)
    (declare #.OPT)
    (macrolet ((line-branches-up (num-list)
                 `(min ,@(mapcar (lambda (x)
                                   `(if (< num ,x)
                                        +undrawable-flag+
                                        (1+ (solve (- num ,x)))))
                                 (sort num-list #'>))
                       (1+ (solve (- num 1))))))
      (if (zerop num)
          0
          (line-branches-up #.(append (loop for pow from 1
                                            for num = (expt 6 pow)
		                            while (<= num 100000)
                                            collect num)
		                      (loop for pow from 1
                                            for num = (expt 9 pow)
                                            while (<= num 100000)
                                            collect num)))))))

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

#-swank(main)


Measured memory_bytes: 12776