Задача D. Марсианские факториалы

Автор:I Всероссийская командная школьников по программированию, 2000 год   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В 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, разделенные пробелом.

Формат выходного файла

Выведите в выходной файл число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

Ограничения

1 ≤ N ≤ 109, 2 ≤ K ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 10
1
2
100 10
24
3
100 6
48
4
3 10
0

0.102s 0.012s 15