Тройка

Вам дано целое число $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\%$ от общего количества баллов.