Minimum Steps to One

You are given an integer \(n\). You need to determine the minimum number of operations required to reduce \(n\) to 1. In one operation, you can perform one of the following:

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

Your task is to compute the minimum number of steps required to reduce \(n\) to 1.

inputFormat

The input consists of a single integer (n) ((1 \le n \le 10^6)) read from standard input.

outputFormat

Output a single integer which is the minimum number of steps required to reduce (n) to 1. The result should be printed to standard output.## sample

10

3