Minimum Operations to Reduce a Number to One

Given a positive integer \(N\), your task is to compute the minimum number of operations required to reduce \(N\) to 1. In each operation, you can perform one of the following actions:

• Subtract 1 from \(N\): \(N := N - 1\).
• If \(N\) is divisible by 2, divide \(N\) by 2: \(N := N/2\).
• If \(N\) is divisible by 3, divide \(N\) by 3: \(N := N/3\).

It is guaranteed that for every input \(N\), there exists a sequence of operations that reduces \(N\) to 1.

Note: All mathematical formulas are written in \( \LaTeX \) format.

inputFormat

The input is read from stdin and consists of a single integer:

• \(N\) \( (1 \le N \le 10^6)\): the number to be reduced to 1.

outputFormat

Print to stdout a single integer representing the minimum number of operations required to reduce \(N\) to 1.

10

3