Над целым числом можно производить следующие операции:
Если число делится на , то разделить его на ;
Если число делится на , то разделить его на ;
Вычесть .
По заданному натуральному числу найдите наименьшее количество операций, после выполнения которых получится .
Каждая строка содержит одно натуральное число .
Для каждого значения в отдельной строке выведите наименьшее количество операций, после выполнения которых получится .