Minimum Operations to One

Given an integer \(N\), your task is to compute the minimum number of operations required to reduce it to 1. You are allowed to perform any of the following operations:

• Subtract 1 from \(N\), that is, \(N \leftarrow N - 1\).
• If \(N\) is divisible by 2, you can divide it by 2: \(N \leftarrow \frac{N}{2}\).
• If \(N\) is divisible by 3, you can divide it by 3: \(N \leftarrow \frac{N}{3}\).

Find the minimum number of operations required to transform \(N\) to 1.

Note: Use dynamic programming to achieve an optimal solution. The operations can be represented mathematically as follows:

\[ dp[i] = \min\big(dp[i-1] + 1,\; dp[\frac{i}{2}] + 1 \; (if\; 2|i),\; dp[\frac{i}{3}] + 1 \; (if\; 3|i)\big) \]

inputFormat

The input consists of a single line containing an integer \(N\) (\(1 \leq N \leq 10^6\)). This \(N\) represents the number you need to reduce to 1 using the allowed operations.

outputFormat

Output a single integer on a line denoting the minimum number of operations required to reduce \(N\) to 1.

10

3