В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K
различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 10
|
1
|
|
2
|
1 2
|
0
|
|
3
|
100 10
|
24
|
|
4
|
1000 10
|
249
|