Трійка

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Примітка

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

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

Оцінювання

Рішення, які працюють правильно для обмежень $1\le n\le 10^5$, набиратимуть $40\%$ балів.