# 문제 풀이에선 d = [0] * 30001을 만들라고 하는데 왜지?
# 다이나믹 프로그래밍으로 풀이해야하는 것을 확인하는 방법!
# 1. 경우의 수가 10000정도~?
# 2. 점층적인 문제 풀이? 재귀로 풀어야하나? 싶을때!
n = int(input())
d = [0] * (n+1)
d[0] = 0
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])
