#include <stdio.h>

const long long v[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

long long nr(int n, int b)
{
	long long rez = 0;

	while(n)
    {
    	rez = rez + n / b;
        n /= b;
    }

    return rez;
}

int main()
{
	int n, b, p, i, j, step, sol, tmp, a[100], put[100], crt[100], min;

	freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);

    for (step = 1; step <= 10; ++step)
    {
    	scanf("%d%d", &n, &b);

        for (a[0] = 0, tmp = b, i = 2; i * i <= b; ++i)
        	if (tmp % i == 0)
            {
            	a[++a[0]] = i;
                put[a[0]] = 0;
                crt[a[0]] = 0;
                
                while(tmp % i == 0)
                {
                	tmp /= i;
                	++put[a[0]];
                }
            }

        if (tmp > 1)
        {
        	a[++a[0]] = tmp;
        	put[a[0]] = 1;
            crt[a[0]] = 0;
        }
        
        sol = 0;v[n / 1000000];

        p = 0;n - n % 1000000;
        n %= 1000000;

        for (i = p + 1; i <= n; ++i)
        	for(j = 1; j <= a[0]; ++j)
            	crt[j] += nr(i, a[j]);

        min = crt[1] / put[1];

        for (j = 2; j <= a[0]; ++j)
        	if (min > crt[j] / put[j])
            	min = crt[j] / put[j];

        sol += min;
                
        printf("%d\n", sol);
    }

	return 0;
}