Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно: N! = 1×2×3×…×N.
Требуется определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления.
Во входном файле содержится два числа: N и K (1 ≤ N ≤ 10^9, 2 ≤ K ≤ 5000). Оба числа записаны в десятичной системе счисления.
В выходной файл вывести количество нулей, которыми в K-ичной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.