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