;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;; -*- coding:utf-8 -*-
(defstruct (queue (:constructor make-queue
                    (&optional list &aux (tail (last list)))))
  (list nil :type list)
  (tail nil :type (or null (cons t null))))

(declaim (inline enqueue))
(defun enqueue (obj queue)
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (setf (cdr tail) (list obj)
              tail (cdr tail))))
  queue)

(declaim (inline dequeue))
(defun dequeue (queue)
  (pop (queue-list queue)))

(defun empty-queue-p (queue)
  (null (queue-list queue)))

(declaim (inline enqueue-front))
(defun enqueue-front (obj queue)
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (push obj list))
    queue))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Body

(declaim (inline digits-sum))
(defun digits-sum (k)
  (loop for n of-type uint62 = k then (floor n 10)
        for d = (mod n 10)
        until (zerop n)
        sum d of-type uint62))

(defun exper (k &optional (size 100000))
  (declare (uint62 size))
  (loop for i from 1 to size
        for num of-type fixnum = k then (+ num k)
        for digits-sum = (digits-sum num)
        minimize digits-sum))

(defun solve (k)
  ;; (num . cost)
  (declare (uint31 k))
  (let ((queue (make-queue))
        (marked (make-array k :element-type 'bit :initial-element 0)))
    (enqueue (cons 1 1) queue)
    (loop until (empty-queue-p queue)
          for (num . cost) of-type (uint32 . uint62) = (dequeue queue)
          do (when (zerop num)
               (return cost))
             (when (zerop (aref marked num))
               (setf (aref marked num) 1)
               (let ((num*10 (mod (* 10 num) k)))
                 (when (zerop (aref marked num*10))
                   (enqueue-front (cons num*10 cost) queue)))
               (let ((num+1 (mod (+ num 1) k)))
                 (when (zerop (aref marked num+1))
                   (enqueue (cons num+1 (+ cost 1)) queue)))))))

(defun main ()
  (let* ((k (read)))
    (println (solve k))))

#-swank(main)


Measured memory_bytes: 27492