#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;

#define INF (1ll<<63)-1

vector < pair <long long ,long long> > f;

void fact(long long  b)
{
	int e=0;
	int d=3;
	
	
	while(b%2==0&&b!=0)
	{
		
		++e;
		b/=2;
	}
	if(e>0)f.push_back(make_pair(2,e));
	
	while((d*d)<=b)
	{
		e=0;
		while(b%d==0)
		{
			
			++e;
			b/=d;
		}
		if(e>0)f.push_back(make_pair(d,e));
		d+=2;
	}
	if(b!=1)f.push_back(make_pair(b,1));

}
int main()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	long long  b,n,x=0,rez,nr,k;

	for(int i=1;i<=10;++i)
	{
		scanf("%lld %lld",&n,&b);
		
		rez=INF;		
		f.clear();
		fact(b);		
		for(long long  j=0;j<(long long )f.size();++j)
		{
			nr=0;		
			
			for(x=f[j].first;n/x ; x*=f[j].first)
			{
				
				k=n/x-1;
				nr+=(k)*(k+1)/2*x+(k+1)*(n-(k+1)*x+1);				
			}
			rez=min(rez,nr/f[j].second);			
		}
		printf("%lld\n",rez);
	}

	return 0;
}