Minimum Steps to One

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

• Subtract 1 from \(n\).
• If \(n\) is even, divide it by 2.
• If \(n\) is divisible by 3, divide it by 3.

Find and output the minimum number of steps required to reduce \(n\) to 1.

Note: The operations can be applied in any order as long as they adhere to the above rules. Use dynamic programming or an appropriate algorithm to solve this problem efficiently.

inputFormat

The input consists of a single integer \(n\) (\(n \geq 1\)) provided via standard input.

outputFormat

Output a single integer --- the minimum number of steps required to reduce \(n\) to 1. The output should be printed to standard output.

10

3