Make It One

For an integer X, you may use the following three operations.

1. If X is divisible by 3, divide X by 3.
2. If X is divisible by 2, divide X by 2.
3. Subtract 1 from X.

Given an integer N, use these operations in any order to make N equal to 1. Find the minimum possible number of operations.

The first line contains an integer N. (1 <= N <= 1,000,000)

Print the minimum number of operations needed.

For N = 10, one optimal sequence is 10 -> 9 -> 3 -> 1, which uses 3 operations.