Трійка

Вам дано ціле число $n$. Також є три види операцій:

1. Зменшити $n$ на $1$.

2. Збільшити $n$ на $1$.

3. Якщо $n$ ділиться націло на $3$, поділити $n$ на $3$.

За яку мінімальну кількість операцій можна зробити число $n$ рівним $1$?

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^{18}$).

Output

Виведіть одне число — мінімальну кількість операцій, за яку можна зробити число $n$ рівним $1$.

Examples

Note

У першому прикладі можна один раз поділити на $3$ і отримаємо $1$.

У другому прикладі можна спочатку двічі зменшити $n$ на $1$, а потім поділити на $3$.