#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;
const ull INFI=1LL<<63;

ull n,b;

inline ull s(ull n,ull p)
{
	ull k=n/p-1;
	return ((k*(k+1))/2)*p+((k+1)*(n-(k+1)*p+1));
}

inline ull nr(ull n,ull p)
{
	ull x=p,aux=s(n,x),sol=0;
	while(aux)
	{
		sol+=aux;
		x*=p;
		aux=s(n,x);
	}
	return sol;
}

int main()
{
    ull i,t,k=0,sol=INFI;
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	for(t=0;t<10;++t,k=0,sol=INFI)
	{
		scanf("%llu %llu\n",&n,&b);
		for(i=2;i*i<=b;++i)
			if(b%i==0)
			{
				k=0;
				while(b%i==0)
				{
				    b/=i;
				    ++k;
                }
				sol=min(sol,nr(n,i)/k);
			}
		if(b>1)
			sol=min(sol,nr(n,b));
		printf("%llu\n",sol);
	}
	return 0;
}