#include<iostream>
#include<fstream>
using namespace std;

long long baza[100001],exp[100001],p,q;

inline void descompunere(long long p)
{
	long long i,l;
	l=0;
	for(i=2;1LL*i*i<=p;i++)
		if(p%i==0) {
			baza[++l]=i;
			while(p%i==0) {
				exp[l]++;
				p=p/i;
			}
			exp[l]=exp[l]*q;
		}
	if(p!=1) {
		baza[++l]=p;
		exp[l]=q;
	}
	baza[0]=l;
}

inline long long putere(long long x, long long n)
{
	long long i,d;
	d=0;
	for(i=x;i<=n;i=1LL*i*i)
		d=d+n/i;
	return d;
}

int verificare(long long x)
{
	long long i;
	for(i=1;i<=baza[0];i++)
		if((long long) putere(baza[i],x)<exp[i])
			return 0;
	return 1;
}

long long cautarebinara()
{
	int d;
	long long st,dr,mij;
	st=1;
	dr=1LL*p*q;
	while(st<dr) {
        mij=(0LL+st+dr)/2;
		d=verificare(mij);
		if(d==1)
			dr=mij;
		else st=mij+1;
	}
	mij=(0LL+st+dr)/2;
	d=verificare(mij);
	if(d==0)
		mij++;
	return mij;
}

int main ()
{
	ifstream f("gfact.in");
	ofstream g("gfact.out");
	f>>p>>q;
	f.close();
	descompunere(p);
	if(1LL*p*q==1)
		g<<"0";
	else g<<cautarebinara();
	g.close();
	return 0;
}