Calculator

Ilya's calculator performs two actions: multiplies the current number by three and adds one to it. The calculator now shows the number $1$. Help Ilya to determine the smallest number of operations, after which he will get the number $n$.

Input

One integer $n(10\le n\le 10^9)$.

Output

Print the minimum number of operations.

Examples