Уменьшающееся число

Над целым числом можно производить следующие операции:

• Если число делится на $3$, то разделить его на $3$;

• Если число делится на $2$, то разделить его на $2$;

• Вычесть $1$.

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

Входные данные

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

Выходные данные

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

Примеры