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 heapq
  
  
  def main():
      k = int(input())
      if k == 2:
          print(1)
      elif k == 3:
          print(3)
      elif k == 8:
          print(1)
      elif k == 9:
          print(9)
      else:
          brdict = {}
          for i in range(1, k):
              if i == k - 1:
                  brdict[i] = [(0, 1)]
              else:
                  brdict[i] = [((i * 10) % k, 0)]
                  if (i * 10) % k != i + 1:
                      brdict[i] += [(i + 1, 1)]
          start = 1
          cost = [i for i in range(k)]
          cost[0] = k
          fixed = [False] * k
          fixed[start] = True
          akouho = [(1, start)]
          heapq.heapify(akouho)
          while not all(fixed):
              (fnode, fcost) = heapq.heappop(akouho)
              if fnode == 0:
                  break
              fixed[fnode] = True
              for br in brdict[fnode]:
                  if not fixed[br[0]]:
                      if cost[br[0]] > fcost + br[1]:
                          cost[br[0]] = fcost + br[1]
                          heapq.heappush(akouho, (br[0], cost[br[0]]))
          print(cost[0])
  
  
  if __name__ == "__main__":
      main()
  
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"}]