e-olymp
Задачи

Факториал

Факториал

Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно: N! = 1×2×3××N.

Требуется определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления.

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

Во входном файле содержится два числа: NиK(1N109, 2K5000).Оба числа записаны в десятичной системе счисления.

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

В выходной файл вывести количество нулей, которыми в K-ичной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
Sample 1
10000  10

Sample 2
10000  2

Sample 3
123456789  4800

Sample 4
27110307  4107
Выходные данные
Sample 1
2499

Sample 2
9995

Sample 3
15432096

Sample 4
376531