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

Each line contains a single positive integer $n(1\le n\le 10^6)$.

Output

For each value of $n$, print the minimum number of operations required to obtain $1$ on a separate line.

Examples