K. Нули факториала

Найдите количество нулей в конце записи числа $N!$ в системе счисления с основанием $K$.

Например, $100!$ в десятичной системе оканчивается $24$ нулями, а в системе с основанием $6$ — уже $48$.

Одна строка содержит числа $N$ и $K$ ($1 \le N \le 10^9$, $2 \le K \le 1000$).

Одно число — количество нулей в конце.