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: def digit_sum(n: int) -> int:
      ans = 0
      while n > 0:
          ans += n % 10
          n //= 10
  
      return ans
  
  
  def judge(n: int) -> int:
      pow2 = [2**i for i in range(21)]
      pow5 = [5**i for i in range(11)]
      pow10 = [10**i for i in range(7)]
  
      if n % 99999 == 0:
          return 9 * 5
      elif n % 9999 == 0:
          return 9 * 4
      elif n % 999 == 0:
          return 9 * 3
      elif n % 99 == 0:
          return 9 * 2
      elif n % 33 == 0:
          return 6
      elif n in pow2:
          return 1
      elif n in pow5:
          return 1
      elif n in pow10:
          return 1
      else:
          ans = 10**10
          for i in range(1, 100000):
              ans = min(ans, digit_sum(i * n))
  
          return ans
  
  
  n = int(input())
  
  
  print(judge(n))
  
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"}]