Minimum Steps to One

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

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

The problem can be efficiently solved using a recursive approach with memoization. Make sure your solution reads input from standard input (stdin) and writes the output to standard output (stdout).

inputFormat

Input is provided as a single line containing a positive integer (N) ((1 \le N \le 10^9)).

outputFormat

Output a single integer denoting the minimum number of steps required to reduce (N) to 1.## sample

10

3