Марсіанські факторіали
У 3141 році чергова експедиція на Марс виявила у одній з печер таємничі знаки. Вони однозначно доводили існування на Марсі розумних істот. Проте смисл цих таємничих знаків довгий час залишався невідомим. Нещодавно один з вчених, професор Дуже-Розумний, помітив один цікавий факт: усього у написах, які складено з цих знаків, зустрічається рівно K різних символів. Більше того, усі написи завершуються на довгу послідовність одних і тих же символів.
Висновок, який зробив зі своїх спостережень професор, потряс усіх вчених Землі. Він припустив, що ці написи є записами факторіалів різних натуральних чисел у системі числення з основою K. А символи у кінці – це, звичайно ж, нулі – адже, як відомо, факторіали великих чисел завершуються великою кількістю нулів. Наприклад, у нашій десятковій системі числення факторіали завершуються на нулі починаючи з 5!=1·2·3·4·5=120. А у числа 100! у кінці йде 24 нулі у десятковій системі числення і 48 нулів у системі числення з основою 6 – так що у припущення професора є розумні підстави!
Тепер вченим терміново потрібна програма, яка за заданими числами N та K знайде кількість нулів у кінці запису в системі числення з основою K числа N!=1·2·3·...·(N-1)·N, щоб вони могли перевірити свою гіпотезу. Вам прийдеться написати їм таку програму!
Вхідні дані
У першому рядку вхідного файлу знаходяться числа N та K, відокремлені пропуском (1 ≤ N ≤ 10^9, 2 ≤ K ≤ 1000).
Вихідні дані
Виведіть у вихідний файл число X - кількість нулів у кінці запису числа N! у системі числення з основою K.