10041 1로 만들기 Silver III

문제

정수 N이 주어졌을 때, 다음 세 가지 연산을 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

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

입력

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

출력

1로 만들기 위한 최소 연산 횟수를 출력한다.

10

3

2

1