output_description: Print the smallest possible sum of the digits in the decimal notation of a
  positive multiple of K.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      K
attempt: import sys
  
  # import math
  # import queue
  # import copy
  # import bisect#2分探索
  from collections import deque
  
  
  def input():
      return sys.stdin.readline()[:-1]
  
  
  def inputi():
      return int(input())
  
  
  K = inputi()
  vals = [10**5 + 1] * K
  visit = []
  vals[1] = 0
  q = deque([1])
  flag = False
  while len(q) > 0:
      s = q.popleft()
      vs = vals[s]
      if s == 0:
          print(vs + 1)
          flag = True
          break
      # visit.append(s)
      s0 = (10 * s) % K
  
      if vs < vals[s0]:
          vals[s0] = vs
          q.appendleft(s0)
      s1 = (s + 1) % K
  
      if vs + 1 < vals[s1]:
          vals[s1] = vs + 1
          q.append(s1)
      # print(q,s,s0,s1,vals)
  
  # if flag==False:
  #    print(vals[0]+1)
  
problem_description: Statement
  
  Find the smallest possible sum of the digits in the decimal notation of a
  positive multiple of K.
samples: [{"input": "6", "output": "3\n    \n\n12=6\u00d72 yields the smallest sum.\n\n* * *"}, {"input": "41", "output": "5\n    \n\n11111=41\u00d7271 yields the smallest sum.\n\n* * *"}, {"input": "79992", "output": "36"}]