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