08-2. 1로 만들기

n = int(input())
data= [0]*3001

# 5, 3, 2 로 나누거나 1 빼기.. 
# 연산한 것이 무엇이 가장 작은지 판별
# +1 은 계산 횟수를 더해주기 위한 것. 
# bottom up 방식이므로.. i//k < i 를 만족해서 다음처럼 표현 가능.. 

for i in range(2,n+1):
  d[i] = d[i-1]+1

  if i %2 == 0:
    d[i] = min(d[i], d[i//2]+1)
  if i %3 == 0:
    d[i] = min(d[i], d[i//3]+1)
  if i %5 == 0:
    d[i] = min(d[i], d[i//5]+1)

print(d[n])