#include <stdio.h>

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

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

    return rez;
}

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

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

    for (step = 1; step <= 10; ++step)
    {
    	scanf("%lld%lld", &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;
                
                while(tmp % i == 0)
                {
                	tmp = tmp / i;
                	++put[a[0]];
                }
            }

        if (tmp > 1)
        {
        	a[++a[0]] = tmp;
        	put[a[0]] = 1;
        }

        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("%lld\n", sol);
    }

	return 0;
}