C. Замыкающие нули
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аки любит числа. Особенно те, что заканчиваются на большое количество нулей. Например, число $$$9200$$$ заканчивается на два нуля. Аки считает, что чем больше таких замыкающих нулей в записи числа, тем лучше.

Однако Аки полагает, что количество замыкающих нулей не постоянно, а зависит от основания системы счисления, которая используется. Поэтому он изучает различные сценарии с разными числами и разными основаниями систем счисления. К настоящему моменту интересующие его числа стали настолько странными, что без вашей помощи ему никак не обойтись.

Вам даны два целых числа $$$n$$$ и $$$b$$$ (записанные в десятичной системе счисления). Выясните, сколько замыкающих нулей в $$$b$$$-ичной (то есть в системе счисления с основанием $$$b$$$) записи числа $$$n\,!$$$ (факториала $$$n$$$).

Входные данные

Единственная строка входных данных содержит два целых числа $$$n$$$ и $$$b$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le b \le 10^{12}$$$).

Выходные данные

Выведите одно целое число — количество замыкающих нулей в $$$b$$$-ичной записи числа $$$n!$$$.

Примеры
Входные данные
6 9
Выходные данные
1
Входные данные
38 11
Выходные данные
3
Входные данные
5 2
Выходные данные
3
Входные данные
5 10
Выходные данные
1
Примечание

В первом примере $$$6!_{(10)} = 720_{(10)} = 880_{(9)}$$$.

Во втором и третьем примерах $$$5!_{(10)} = 120_{(10)} = 1111000_{(2)}$$$.

Последовательность $$$d_1, d_2, \ldots, d_k$$$ называется представлением числа $$$x$$$ в $$$b$$$-ичной системе счисления, если $$$x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$$$, где $$$d_i$$$ являются целыми числами и $$$0 \le d_i \le b - 1$$$. Например, число $$$720$$$ из первого примера имеет представление $$$880_{(9)}$$$ так как $$$720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$$$.

Вы можете прочитать ещё о системах счисления здесь.