1로 만들기

정수 X에 대해 다음 세 가지 연산을 사용할 수 있다.

1. X가 3으로 나누어떨어지면 X를 3으로 나눈다.
2. X가 2로 나누어떨어지면 X를 2로 나눈다.
3. X에서 1을 뺀다.

정수 N이 주어질 때, 위 연산들을 적절히 사용해 N을 1로 만들려고 한다. 필요한 연산 횟수의 최솟값을 구하라.

첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

첫째 줄에 필요한 연산 횟수의 최솟값을 출력한다.

N = 10이면 10 -> 9 -> 3 -> 1 순서로 3번의 연산만에 1을 만들 수 있다.