Факторіалом натурального числа N (позначається N!) називається добуток всіх натуральних чисел від 1 до N включно: N! = 1×2×3×…×N.
Потрібно визначити, якою кількістю цифр "0" закінчується запис числа N! у K-ій системі числення.
У вхідному файлі міститься два числа: N и K (1 ≤ N ≤ 10^9, 2 ≤ K ≤ 5000). Обидва числа записані у десятковій системі числення.
У вихідний файл вивести кількість нулів, якими у K-ій системі числення закінчується число N!. Число вивести у десятковій системі числення.