Число що зменшується

Над цілим числом можна здійснювати наступні операції:

• Якщо число ділиться на $3$, то розділити його на $3$;

• Якщо число ділиться на $2$, то розділити його на $2$;

• Відняти $1$.

За заданоим натуральним числом $n$ знайти найменшу кількість операцій, після виконання яких отримаємо $1$.

Вхідні дані

Кожний рядок містить одне натуральне число $n(1\le n\le 10^6)$.

Вихідні дані

Для кожного значення $n$ в окремому рядку вивести найменшу кількість операцій, після виконання яких отримаємо $1$.

Приклади