n = int(input())
dp = [0]*30001

# 상향식(바텀업) DP
for i in range(2,n+1):
    # 1을 뺄 때
    dp[i] = dp[i-1] + 1
    # 2로 나눌 때
    if i % 2 == 0:
        dp[i] = min(dp[i],dp[i//2]+1)
    # 3으로 나눌 때
    if i % 3 == 0:
        dp[i] == min(dp[i],dp[i//3]+1)
    # 5로 나눌 때
    if i % 5 == 0:
        dp[i] == min(dp[i],dp[i//5]+1)

print(dp[n])