There are three types of operations that can be performed on an integer: \begin{itemize} \item If the number is divisible by $3$, divide it by $3$; \item If the number is divisible by $2$, divide it by $2$; \item Subtract $1$. \end{itemize} For a given positive integer $n$, find the minimum number of operations required to obtain $1$. \InputFile Each line contains a single positive integer $n~(1 \le n \le 10^6)$. \OutputFile For each value of $n$, print the minimum number of operations required to obtain $1$ on a separate line.