Minimum Operations to Reduce an Integer to One

You are given a positive integer \(n\). Your goal is to reduce \(n\) to 1 using a minimum number of operations. At each step, you may perform one of the following operations:

• If \(n\) is divisible by 2, you may replace \(n\) with \(\frac{n}{2}\).
• If \(n\) is divisible by 3, you may replace \(n\) with \(\frac{n}{3}\).
• Subtract 1 from \(n\), i.e. replace \(n\) with \(n - 1\).

Find the minimum number of operations required to reduce \(n\) to 1.

Note: The operations are counted as follows: each valid operation (division or subtraction) counts as one step.

inputFormat

The input consists of a single line containing an integer \(n\) (\(1 \leq n \leq 10^6\)).

outputFormat

Output a single integer representing the minimum number of operations needed to reduce \(n\) to 1.

## sample

10

3

</p>