白駿14631に作成

# n을 1로 만드는 최소 횟수를 리턴하는 함수
def make_one(n):
    # i는 1부터 n까지 반복
    for i in range(2, n + 1):
        # dp[i] = min(dp[i // 3], dp[i // 2], dp[i - 1]) + 1
        # (i를 1로 만드는 최소 횟수)를 (i - 1을 1로 만드는 최소 횟수) + 1로 설정
        dp[i] = dp[i - 1] + 1
        # i가 3의 배수이고 (i를 1로 만드는 최소 횟수)가 (i // 3을 1로 만드는 최소 횟수) + 1보다 크다면
        if i % 3 == 0 and dp[i] > dp[i // 3] + 1:
            # (i를 1로 만드는 최소 횟수)를 (i // 3을 1로 만드는 최소 횟수) + 1로 갱신
            dp[i] = dp[i // 3] + 1
        # elif가 아님에 주의. 위와 아래 조건문은 각각 실행되어야 함
        # i가 2의 배수이고 (i를 1로 만드는 최소 횟수)가 (i // 2를 1로 만드는 최소 횟수) + 1보다 크다면
        if i % 2 == 0 and dp[i] > dp[i // 2] + 1:
            # (i를 1로 만드는 최소 횟수)를 (i // 2를 1로 만드는 최소 횟수) + 1로 갱신
            dp[i] = dp[i // 2] + 1
    # n을 1로 만드는 최소 횟수의 값을 리턴
    return dp[n]


# 입력되는 N이 최대 10^6이므로 리스트의 크기를 10^6 + 1로 생성
dp = [0] * int(10e6 + 1)
# 정수 N 입력
N = int(input())
# N을 1로 만드는 최소 횟수를 받음
result = make_one(N)
# 정답 출력
print(result)

# n을 1로 만드는 최소 횟수를 리턴하는 함수
def make_one(n):
    # i는 1부터 n까지 반복
    for i in range(2, n + 1):
        # dp[i] = min(dp[i // 3], dp[i // 2], dp[i - 1]) + 1
        # (i를 1로 만드는 최소 횟수)를 (i - 1을 1로 만드는 최소 횟수) + 1로 설정
        dp[i] = dp[i - 1] + 1
        # i가 3의 배수이면
        if i % 3 == 0:
            # (i를 1로 만드는 최소 횟수)는 자기 자신과 (i // 3을 1로 만드는 최소 횟수) + 1 중 작은 것으로 갱신
            dp[i] = min(dp[i], dp[i // 3] + 1)
        # elif가 아님에 주의. 위와 아래 조건문은 각각 실행되어야 함
        # i가 2의 배수이면
        if i % 2 == 0:
            # (i를 1로 만드는 최소 횟수)는 자기 자신과 (i // 2를 1로 만드는 최소 횟수) + 1 중 작은 것으로 갱신
            dp[i] = min(dp[i], dp[i // 2] + 1)
    # n을 1로 만드는 최소 횟수의 값을 리턴
    return dp[n]


# 입력되는 N이 최대 10^6이므로 리스트의 크기를 10^6 + 1로 생성
dp = [0] * int(10e6 + 1)
# 정수 N 입력
N = int(input())
# N을 1로 만드는 최소 횟수를 받음
result = make_one(N)
# 정답 출력
print(result)

# 메모리 초과
# 하향식 방법은 파이썬으로 안 되는 듯
import sys

# 재귀함수의 깊이 설정
sys.setrecursionlimit(10 ** 6)


# n을 1로 만드는 최소 횟수를 리턴하는 함수
def make_one(n):
    # n이 1이면 0을 리턴
    if n == 1:
        return 0
    # n에 해당하는 값이 있으면 리턴
    if dp[n] > 0:
        return dp[n]
    # (n을 1로 만드는 최소 횟수)를 (n - 1을 1로 만드는 최소 횟수) + 1로 초기화
    dp[n] = make_one(n - 1) + 1
    # n이 3의 배수이면
    if n % 3 == 0:
        # (n // 3을 1로 만드는 최소 횟수) + 1의 값을 tmp에 저장
        tmp = make_one(n // 3) + 1
        # (현재 n을 1로 만드는 최소 횟수)가 tmp의 값보다 크면 tmp의 값으로 갱신
        if dp[n] > tmp:
            dp[n] = tmp
    # n이 2의 배수이면
    if n % 2 == 0:
        # (n // 2을 1로 만드는 최소 횟수) + 1의 값을 tmp에 저장
        tmp = make_one(n // 2) + 1
        # (현재 n을 1로 만드는 최소 횟수)가 tmp의 값보다 크면 tmp의 값으로 갱신
        if dp[n] > tmp:
            dp[n] = tmp
    # 그렇게 구한 dp[n]의 값을 리턴
    return dp[n]


# 입력되는 N이 최대 10^6이므로 리스트의 크기를 10^6 + 1로 생성
dp = [0] * int(10e6 + 1)
# 정수 N 입력
N = int(input())
# N을 1로 만드는 최소 횟수를 받음
result = make_one(N)
# 정답 출력
print(result)