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.
One integer n (10≤n≤109).
Print the minimum number of operations.