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: n = int(input())
  
  while n % 2 == 0:
      n //= 2
  while n % 5 == 0:
      n //= 5
  if n == 1:
      print(1)
  else:
      X = [n for i in range(n)]
  
      j = 1
      s = 1
      post = []
      m = 0
      while True:
          s *= 10
          s %= n
          post.append(s)
          X[s] = min(j, X[s])
          m += 1
          if s == 1:
              break
      ans = 0
      while True:
          if ans > 0:
              break
          pre = post
          post = []
          j += 1
          for p in pre:
              pp = (p + 1) % n
              if pp == 0:
                  X[0] = j
                  ans = j
                  break
              if X[pp] == n:
                  for i in range(m):
                      post.append(pp)
                      X[pp] = j
                      pp *= 10
                      pp %= n
      print(ans)
  
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"}]