1로 줄이기

정수 N이 주어져요. 아래 연산들을 원하는 순서로 반복해서 N을 1로 만들려고 해요.

• 나누기 3: N이 3의 배수일 때만 사용할 수 있어요. N을 3으로 나눠요.
• 나누기 2: N이 2의 배수일 때만 사용할 수 있어요. N을 2로 나눠요.
• 빼기 1: 항상 사용할 수 있어요. N에서 1을 빼요.

1이 될 때까지 필요한 연산의 최소 횟수를 구해보세요.

입력

정수 N이 주어져요.

• $1 \leq N \leq 10^6$

출력

연산 횟수의 최솟값을 출력하세요.