Problems
Decreasing Number
Decreasing Number
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.
Input data
Each line contains a single positive integer n~(1 \le n \le 10^6).
Output data
For each value of n, print the minimum number of operations required to obtain 1 on a separate line.
Examples
Input example #1
1 5 10
Output example #1
0 3 3