#include <stdio.h>

long long nr(int n, int p)
{
	long long rez = 0;
    int i, tmp;

    for (tmp = p; n >= tmp; tmp *= p)
    	rez += p * (n / tmp) * (n / tmp - 1) / 2 + (n % tmp + 1) * (n / tmp);

    return rez;
}

int main()
{
	int n, b, i, step, sol, tmp, put[16], crt[16], a[16];

	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;
        }

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

        sol = -1;

        for (i = 1; i <= a[0]; ++i)
        	if (sol == -1 || sol > crt[i] / put[i])
            	sol = crt[i] / put[i];

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

	return 0;
}