Water Calculator

Task

William has recently built a Water Calculator${}^{TM}$, which mimics the operation of a computer through water pipes, sinks and siphons. Due to the rudimentary nature of its circuits, the Water Calculator${}^{TM}$ is able to store a single number up to a billion and perform only a handful of atomic operations:

• add or subtract $1$;
• multiply by $2$;
• divide by a power of $3$ (which divides exactly the stored number).

These few operations are anyway more than sufficient for William's basic mathematical needs.

In this moment, the Water Calculator${}^{TM}$ is holding number $N$. Since William needs to leave his home for a while, it is crucial to empty the calculator in order to avoid malicious rusting! Calculate the minimum number of atomic operations necessary for William to completely empty the calculator.

Input data

The first and only line contains the only integer $N$.

Output data

You need to write a single line with an integer: the minimum number of atomic operations needed to empty the Water Calculator${}^{TM}$.

Constraints and clarifications

• $1 \le N \le 10\,000\,000$.
• Operations that would increase the number stored over $10^9$ are not allowed.

Example 1

stdin

13

stdout

4

Explanation

In the first sample case, a possible sequence of operations is the following: $13 \rightarrow 26 \rightarrow 27 \rightarrow 1 \rightarrow 0$

Example 2

stdin

81

stdout

2

Explanation

In the second sample case, a single operation brings $81$ to $1$ and a second one to $0$.