[이코테] 1로 만들기

x = int(input())

d = [0] * 30001

for i in range(2, x + 1):
  a, b, c = 2, 3, 5
  # 현재의 수에서 1을 빼는 경우
  d[i] = d[i - 1] + 1
  # 현재의 수가 2로 나누어 떨어지는 경우
  if i % a == 0:
    d[i] = min(d[i], d[i//a] + 1)
  # 현재의 수가 3로 나누어 떨어지는 경우
  if i % b == 0:
    d[i] = min(d[i], d[i//b] + 1)
  # 현재의 수가 5로 나누어 떨어지는 경우
  if i % c == 0:
    d[i] = min(d[i], d[i//c] + 1)

print(d[x])