Minimum Reduction Steps to One

You are given a positive integer N. Your task is to determine the minimum number of steps required to reduce N to 1. In each step, you may perform one of the following operations:

• Subtract 1 from the number.
• If the number is divisible by 2, divide it by 2. That is, if \(N \bmod 2 = 0\), then you may set \(N = \frac{N}{2}\).
• If the number is divisible by 3, divide it by 3. That is, if \(N \bmod 3 = 0\), then you may set \(N = \frac{N}{3}\).

For example, if N = 10, one possible sequence is: 10 \(\to\) 9 \(\to\) 3 \(\to\) 1, which takes 3 steps. Your solution should compute the minimum number of steps required to reach 1.

inputFormat

The input consists of a single positive integer N provided via standard input.

outputFormat

Output a single integer representing the minimum number of steps required to reduce N to 1 using the allowed operations. The output should be written to standard output.## sample

10

3