В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5! = 1·2·3·4·5 = 120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!
Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N! = 1·2·3·…·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!
Входные данные
Входной файл INPUT.TXT содержит числа N и K, разделенные пробелом. (1 ≤ N ≤ 109, 2 ≤ K ≤ 1000).
Выходные данные
Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.
Примеры
№INPUT.TXT
15 10
2100 10
3100 6
43 10
№ OUTPUT.TXT
1 1
2 24
3 48
4 0
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5! = 1·2·3·4·5 = 120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!
Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N! = 1·2·3·…·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!
Входные данные
Входной файл INPUT.TXT содержит числа N и K, разделенные пробелом. (1 ≤ N ≤ 109, 2 ≤ K ≤ 1000).
Выходные данные
Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.
Примеры
№INPUT.TXT
15 10
2100 10
3100 6
43 10
№ OUTPUT.TXT
1 1
2 24
3 48
4 0