Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=62) крокрыскоинов, 216(=63) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=92) крокрыскоинов, 729(=93) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.
Входные данные
На вход подается целое число N (\(1<=N<=100000\)).
Выходные данные
Выведите ответ на задачу.