Геральд на досуге занимается продажей государственных секретов. Все секреты стоят одинаково: n марок. В государстве, продажей секретов которого занимается Геральд, нет купюр, есть только монеты. Зато есть монеты всех положительных целых номиналов, являющихся степенями тройки: 1 марка, 3 марки, 9 марок, 27 марок и так далее. Монет других номиналов в обращении нет. Конечно, Геральд любит, когда ему дают без сдачи. И все покупатели уважают его и стараются давать нужную сумму без сдачи, если это возможно. Но такое бывает не всегда.
Однажды к нему пришел незадачливый покупатель, у которого не нашлось нужной суммы без сдачи. Тогда он постарался из имеющихся у него монет выдать Геральду большую, чем надо сумму как можно меньшим количеством монет. Какое максимальное количество монет у него могло получиться?
Формальное объяснение предыдущего абзаца: рассмотрим все возможные комбинации монет, при которых покупатель не может дать Геральду сумму в n марок без сдачи. Для каждой такой комбинации посчитаем, каким минимальным количеством монет покупатель может набрать хотя бы n марок. Среди всех комбинаций выберем максимум по минимальному количеству монет. Это число нас и интересует.
Выходные данные
В единственной строке выведите целое число: максимальное число монет, которым мог расплатиться незадачливый покупатель.
Примечание
В первом тестовом примере, у покупателя не может быть монеты в 1 марку, так как тогда бы он мог выдать точную сумму. Он выдаст ровно одну монету, так как он стремится дать как можно меньше монет, а любая другая монета уже дает большую сумму.
Во втором тестовом примере, если бы у покупателя были в наличии ровно три монеты по 3 марки, тогда, чтобы отдать Геральду 4 марки, придется отдать две из этих монет. Три монеты отдать нельзя, потому что покупатель стремится минимизировать количество монет, которые он отдаст из имеющихся у него.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
4
|
2
|