#include <cstdio>
#include <cstring>
#include <cmath>

#define file_in "zero2.in"
#define file_out "zero2.out"

#define Nmax 1000100
#define Inf 10000000000000000LL

int n,i,N,B,d,e,v[Nmax],nrp,nrf,j,max,t,k;
long long suma,min,put,x;

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
		 
	for (t=1;t<=10;++t)
    {
	
		scanf("%d %d", &N, &B);

		//printf("%d\n", B);
		memset(v,0,sizeof(v));
		//descompune B
		max=0;
		d=2;
		e=0;
		while(B%d==0)
		{
			e++;
			B/=d;
		}
		if (e>0)
		{
			max=d;
			v[d]=e;
		}
		
		d=3;
		while(B!=1)
		{
			 e=0;
		     while(B%d==0)
		     {
			    e++;
			    B/=d;
		     }
		     if (e>0)
		     {
			   max=d;
			   v[d]=e;
		     }
		d+=2;
		}
		
		
		min=Inf;
		
		//for (i=1;i<=max;++i) if (v[i]>0)printf("%d %d\n", i, v[i]); 
		
		for (i=2;i<=max;++i)
		if (v[i]>0)
		{
			put=i;
			suma=0;
			x=1;
			while(x!=0)
			{
			k=trunc(N/put)-1;
			x=k*(k+1)/2*put+(k+1)*(N-(k+1)*put+1);
			suma+=x;
			put*=i;
			}
			
			if ((suma/v[i])<min)
				min=(suma/v[i]);
		}
		
		printf("%lld\n", min);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}