#include<cstdio>
long long n,p,d[25];
long long f(long long k)
{
	long long n1,s1=k,p1=1,nr,num,j,s=0,i;
	short int v[25];
	for(i=0;i<=d[0];i++)
		v[i]=0;
	num=1<<d[0];
	for(nr=1;nr<num;nr++)
	{
		for(i=d[0];i>=0;--i)
			if(v[i]==0)
				break;
		v[i]=1;
		for(j=i+1;j<=d[0];j++)
			v[j]=0;
		n1=0;
		p1=1;
		for(i=1;i<=d[0];i++)
		{
			n1+=v[i];
			if(v[i]==1)
				p1=p1*d[i];
		}
		s1=k/p1;
		if(n1%2==0)
			s-=s1;
		else
			s+=s1;
	}
	return k-s;
}
long long cb(long long p)
{
	long long i,pas= (long long) 1<<61;
	for(i=0;pas!=0;pas>>=1)
		if(f(i+pas)<p)
			i+=pas;
	return 1+i;
}
int main()
{
	int i;
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	if(n==1)
	{	
		printf("%lld",p);
		return 0;
	}
	
	i=2;
	d[0]=0;
	while(n>1)
	{
		if(n%i==0)
			d[++d[0]]=i;;
		while(n%i==0)
		{
			n=n/i;
		}
		i++;
	}
	printf("%lld",cb(p));
	return 0;
}