Trio

You are given an integer $n$. You can perform the following three types of operations:

1. Decrease $n$ by $1$.

2. Increase $n$ by $1$.

3. If $n$ is divisible by $3$, divide $n$ by $3$.

Determine the minimum number of operations needed to transform the number $n$ into $1$.

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.