# 1로 만들기

# a. X가 5로 나누어떨어지면, 5로 나눈다.
# b. X가 3으로 나누어떨어지면, 3으로 나눈다.
# c. X가 2로 나누어떨어지면, 2로 나눈다.
# d. X에서 1을 뺀다.

# 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다,. 연산을 사용하는 횟수의 최소값을 출력하시오.

# 입력 예시
# 26

# 출력 예시
# 3

x = int(input())
# DP테이블 초기화
d = [0] * 30001

for i in range(2, x+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[x])