output_description: Print the first three characters of the label of the N-th round of AtCoder
  Beginner Contest.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: n_max = 100000
  
  bs = [(6**i, 6) for i in range(1, 10)]
  bs.extend([(9**i, 9) for i in range(1, 10)])
  bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
  bms = []
  s = 5
  for b, i in bs:
      s += b * (i - 1)
      bms.append((b, i, s))
  
  # print(bs)
  # print(bms, len(bms))
  
  # m = 44852
  m = int(input())
  
  stack = [(m, 0, len(bms) - 1)]
  # print("search start!")
  result = 10000
  while stack:
      m, n, bms_i = stack.pop()
      b, i, s = bms[bms_i]
      # print(m, n, bms_i, b, i, s)
  
      if n > result:
          #        print("skip!", m, n, bms_i)
          continue
      if bms_i < 0:
          if m < 6 and result > m + n:
              result = m + n
          #            print('get result!', result)
          continue
  
      for j in range(0, i):
          next_m = m - b * j
          if next_m > 0 and n + j < result:
              stack.append((next_m, n + j, bms_i - 1))
  
  print(result)
  
problem_description: Statement
  
  Decades have passed since the beginning of AtCoder Beginner Contest.
  
  The contests are labeled as `ABC001`, `ABC002`, ... from the first round, but
  after the 999-th round `ABC999`, a problem occurred: how the future rounds
  should be labeled?
  
  In the end, the labels for the rounds from the 1000-th to the 1998-th are
  decided: `ABD001`, `ABD002`, ..., `ABD999`.
  
  You are given an integer N between 1 and 1998 (inclusive). Print the first
  three characters of the label of the N-th round of AtCoder Beginner Contest.
samples: [{"input": "999", "output": "ABC\n    \n\nThe 999-th round of AtCoder Beginner Contest is labeled as `ABC999`.\n\n* * *"}, {"input": "1000", "output": "ABD\n    \n\nThe 1000-th round of AtCoder Beginner Contest is labeled as `ABD001`.\n\n* * *"}, {"input": "1481", "output": "ABD\n    \n\nThe 1481-th round of AtCoder Beginner Contest is labeled as `ABD482`."}]