8-2. 1로 만들기

x = int(input())

d = [0]*30001

for i in range(2, x+1):  # 1로 만드니까 2부터시작
    d[i] = d[i-1]+1  # 가정 (최소연산횟수)
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2]+1)  # 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[x])