#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
struct MyStruct{long long d,e;};
vector<MyStruct> v;
MyStruct make(long long a,long long b)
{
	MyStruct x;
	x.d=a;x.e=b;
	return x;
}
void descomp(long long p,long long q)
{
	long long e,d=2,lim=(long long)sqrt((double)p);
	while(d<=lim && p>1)
	{
		e=0;
		while(p%d==0) {p=p/d;e++;}
		if(e) v.push_back(make(d,e*q));
		d++;
	}
	if(p>1) v.push_back(make(p,q));
}
long long power(long long d,long long n)
{
	long long e=0,p=d;
	while(p<=n)
	{
		e=e+n/p;
		p=p*d;
	}
	return e;
}
bool ok(long long x)
{
	long long d,e;
	vector<MyStruct>::iterator it;
	for(it=v.begin();it!=v.end();it++)
	{
		d=it->d;e=it->e;
		if(power(d,x)<e)
			return 0;
	}
	return 1;
}
long long bs(long long st,long long dr)
{
	long long a,med=st+(dr-st)/2;
	if(st>dr) return -1;
	if(ok(med))
	{
		a=bs(st,med-1);
		if(a!=-1) return a;
		return med;
	}
	else
		return bs(med+1,dr);
}
int main()
{
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	long long p,q;
	scanf("%lld%lld",&p,&q);
	descomp(p,q);
	printf("%lld\n",bs(1,1ll<<62));
}