В деревне Летовецк, где живут мудрые старцы и их ученики, существует древний банк, который хранит богатства в виде ле́токоинов — особых монет, обладающих магической силой. Однако банк установил строгие правила: чтобы снять деньги, нужно использовать только определённые суммы за одну операцию:
-
за одну операцию можно снять только 1 ле́токоин,
-
за одну операцию можно снять сумму 6x, где x - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),
-
за одну операцию можно снять сумму 9x, где x - любое натуральное число (можно снять сумму равную 9, 81, 729, ...).
Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?
Примечание: невозможно повторно вносить снятые деньги в банк!
Формат входных данных
На вход подается целое число
N (
\(1<=N<=100000\)).
Формат выходных данных
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
127 |
4 |
При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции. |
| 2 |
3 |
3 |
1+1+1 = 3, всего 3 операции |
| 3 |
44852 |
16 |
|