Trio

Input

The input consists of a single integer $n$ (1 \le n \le 10^{18}).

Output

Output a single integer representing the minimum number of operations required to make the number $n$ equal to $1$.

Examples

Note

In the first example, you can divide by $3$ once to reach $1$.

In the second example, you can decrease $n$ by $1$ twice, and then divide by $3$.

Scoring

Solutions that correctly handle the constraints 1 \le n \le 10^5 will earn $40\%$ of the total points.