https://www.acmicpc.net/problem/1463
# 중요포인트: 연산수만 가지고 비교함. 실제 n이 어떻게 줄어들었는지는 고려X
'''d[2]=1 (2/2)
d[3]=1 (3/3)
d[4]=2 (4/2 -> 2/2)
d[5]=3 (5-1 -> 4/2 -> 2/2)
d[6]=2 (6/3 -> 2/2) (= 1 + d[6//3])
d[7]=3 (7-1 -> 6/3 -> 2/2) (= 1 + d[6])'''
n = int(input())
d = [0] * (n+1)
for i in range(2, n+1):
d[i] = d[i-1] + 1 # 1 더하는 이유: 기본적으로 연산 한번은 하니까
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)# 1 더하는 이유:d리스트는 최소 "연산수" 니까(1을빼면 연산수는+1돼서)
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1) #위와 동일
print(d[n])