#include <fstream>
#include <vector>
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
#define inf (1LL<<60)-1
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define ll long long
vector <pair <ll,ll> > prim;
ll n, b, val;

void solve()
{
	ll i, x, nr;
	prim.clear();
	for(i=2;i*i<=b;++i)
		if(b%i==0)
		{
			for(nr=0;b%i==0;b/=i)
				++nr;
			prim.pb(mp(i,nr));
		}
	if(b>1)
		prim.pb(mp(b,1));
	val=inf;
	
	for(i=0;i<prim.size();++i)
	{
		nr=0;
		
		for(x=prim[i].fs; n/x ;x*=prim[i].fs)
			nr+=(n/x-1)*(n/x)/2*x+(n/x)*(n-(n/x)*x+1);
		val=min(val,nr/prim[i].sc);
	}

	fout<<val <<'\n';
}

int main()
{
	int i=10;
	for(;i;--i)
	{
		fin>>n >>b;
		solve();
	}
	return 0;
}