Модуль: 11.1d Динамическое программирование. Часть 4_Одномерная динамика

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно 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

 

Напишите программу