A. Секреты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Геральд на досуге занимается продажей государственных секретов. Все секреты стоят одинаково: n марок. В государстве, продажей секретов которого занимается Геральд, нет купюр, есть только монеты. Зато есть монеты всех положительных целых номиналов, являющихся степенями тройки: 1 марка, 3 марки, 9 марок, 27 марок и так далее. Монет других номиналов в обращении нет. Конечно, Геральд любит, когда ему дают без сдачи. И все покупатели уважают его и стараются давать нужную сумму без сдачи, если это возможно. Но такое бывает не всегда.

Однажды к нему пришел незадачливый покупатель, у которого не нашлось нужной суммы без сдачи. Тогда он постарался из имеющихся у него монет выдать Геральду большую, чем надо сумму как можно меньшим количеством монет. Какое максимальное количество монет у него могло получиться?

Формальное объяснение предыдущего абзаца: рассмотрим все возможные комбинации монет, при которых покупатель не может дать Геральду сумму в n марок без сдачи. Для каждой такой комбинации посчитаем, каким минимальным количеством монет покупатель может набрать хотя бы n марок. Среди всех комбинаций выберем максимум по минимальному количеству монет. Это число нас и интересует.

Входные данные

В единственной строке содержится целое число n (1 ≤ n ≤ 1017).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

В единственной строке выведите целое число: максимальное число монет, которым мог расплатиться незадачливый покупатель.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
4
Выходные данные
2
Примечание

В первом тестовом примере, у покупателя не может быть монеты в 1 марку, так как тогда бы он мог выдать точную сумму. Он выдаст ровно одну монету, так как он стремится дать как можно меньше монет, а любая другая монета уже дает большую сумму.

Во втором тестовом примере, если бы у покупателя были в наличии ровно три монеты по 3 марки, тогда, чтобы отдать Геральду 4 марки, придется отдать две из этих монет. Три монеты отдать нельзя, потому что покупатель стремится минимизировать количество монет, которые он отдаст из имеющихся у него.