1로 만들기

첫 줄에 정수 n (1 이상 1000000 이하) 이 주어집니다.

정수 n 에 다음 세 연산을 적용할 수 있습니다.

• 3 으로 나누어떨어지면 3 으로 나눈다
• 2 로 나누어떨어지면 2 로 나눈다
• 1 을 뺀다

n 을 1 로 만드는 데 필요한 연산의 최소 횟수를 출력하세요.

예시

입력

10

출력

3

10

3

1

0