Трійка

Input

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

Output

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

Examples

3

1

5

3

Note

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

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