Факторіал

Факторіалом натурального числа N (позначається N!) називається добуток всіх натуральних чисел від 1 до N включно: N! = 1×2×3×…×N.

Потрібно визначити, якою кількістю цифр "0" закінчується запис числа N! у K-ій системі числення.

Вхідні дані

У вхідному файлі міститься два числа: N и K (1 ≤ N ≤ 10^9, 2 ≤ K ≤ 5000). Обидва числа записані у десятковій системі числення.

Вихідні дані

У вихідний файл вивести кількість нулів, якими у K-ій системі числення закінчується число N!. Число вивести у десятковій системі числення.

Приклади