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

• 1 грн

• 6 грн, \(6^2\) грн, \(6^3\) грн, ....

• 9 грн, \(9^2\) грн, \(9^3\) грн, ....

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

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

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

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

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

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

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

127

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

4