Щоб ускладнити виведення грошей, деякий креативний банк дозволяє своїм клієнтам зняти лише одну з таких сум за одну операцію:

• 1 грн

• 6 грн, ~6^2~ грн, ~6^3~ грн, ....

• 9 грн, ~9^2~ грн, ~9^3~ грн, ....

Яка мінімальна кількість операцій потрібна для того, що зняти рівно ~N~ гривень.

Не дозволяється зняті гроші знову класти в банк.

Формат вхідних даних

Вхідний потік містить ціле число ~N~ ~(1 \le N \le 10^5)~

Формат вихідних даних

У вихідний потік вивести мінімальну кількість операцій.

Приклад вхідних даних

127

Приклад вихідних даних

4