#include<stdio.h>
#define NMAX 2305843009213693952LL
#include<math.h>
long long m;
long f[500001];
long long g[500001];
void desc (long p)
{
	long d,lim,ex;
	lim=sqrt(p);
	d=2;
	ex=0;
	while (p%d==0)
	{
		p=p/d;
		ex++;
	}
	if (ex)
	{
		f[++f[0]]=d;
		g[++g[0]]=ex;
	}
	d=3;
	while (p>1 && d<=lim)
	{
		ex=0;
		while (p%d==0)
		{
			p=p/d;
			ex++;
		}
		if (ex)
		{
			f[++f[0]]=d;
			g[++g[0]]=ex;
		}
		d++;
	}
	if (p>1)
	{
		f[++f[0]]=p;
		g[++g[0]]=1;
	}
}

long long multi2 (long k)
{
	long long numitor,s=0;
	numitor=k;
	while (m/numitor)
	{
		s=s+m/numitor;
		numitor=numitor*k;
	}
	return s;
}

long long multi ()
{
	long i;
	long long h;
	for (i=1;i<=f[0];i++)
	{
		h=multi2(f[i]);
		if (h<g[i])
			return 0;
	}
	return 1;
}


long long cautbin (long long st , long long dr)
{
	long long poz=-1;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (multi()==0)
			st=m+1;
		else
		{
			poz=m;
			dr=m-1;
		}
	}
	return poz;
}

long part (long st , long dr)
{
	long i,j,aux,m,p;
	i=st-1;
	j=dr+1;
	m=(st+dr)/2;
	p=f[m];
	while (1)
	{
		do {++i;}while (f[i]<p);
		do {--j;}while (f[j]>p);
		if (i<j)
		{
			aux=f[i];
			f[i]=f[j];
			f[j]=aux;
			aux=g[i];
			g[i]=g[j];
			g[j]=aux;
		}
		else
			return j;
	}
}

void quick (long st , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part(st,dr);
		quick (st,sp);
		quick (sp+1,dr);
	}
}


int main()
{
	long long p,q,b,i;
	
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	
	scanf("%lld%lld",&p,&q);
	desc(p);
	for (i=1;i<=g[0];i++)
		g[i]=g[i]*q;
	quick (1,f[0]);
	b=cautbin(1,NMAX);
	printf("%lld",b);
	return 0;
}