There are three types of operations that can be performed on an integer:
If the number is divisible by 3, divide it by 3;
If the number is divisible by 2, divide it by 2;
Subtract 1.
For a given positive integer n, find the minimum number of operations required to obtain 1.
Each line contains a single positive integer n (1≤n≤106).
For each value of n, print the minimum number of operations required to obtain 1 on a separate line.