eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Факториал

Факториал

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

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

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

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

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

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

Пример

Входные данные #1
10000  10
Выходные данные #1
2499