#include<stdio.h>
#include<vector>
#include<math.h>
#define LL long long
LL fact[69]; 

void desc(LL n)
{
	LL d=2,lim=sqrt(n);
	while(n>1 && d<=lim)
	{
		if(n%d==0)
		{
			fact[++fact[0]]=d;
			while(n%d==0)
				n/=d;
		}
		d++;
	}
if(n>1)
	fact[++fact[0]]=n;
}

LL prod[(LL)1<<20];

using namespace std;

LL nr(LL x)
{
	int i;
	LL sol=0;
	for(i=1;i<=prod[0];i++)
		sol+=x/prod[i];
	return x-sol;
}

int main()
{
	LL i,n,p,st,dr,m,num,j,sol=-1;
	
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	
	scanf("%lld%lld",&n,&p);
	
	desc(n);
	for(i=1;i<(LL)1<<fact[0];i++)
	{
		prod[0]++; prod[prod[0]]=1;
		for(j=0;j<fact[0];i++)
			if(i&((LL)1<<j))
				prod[prod[0]]=prod[prod[0]]*fact[j+1]*(-1);
		prod[prod[0]]*=(-1);
	}
	st=1,dr=(LL)1<<61; 
	while(st<=dr)
	{
		m=(st+dr)>>1;
		num=nr(m);
		if(num>p)
			dr=m-1;
		if(num<p)
			st=m+1;
		if(num==p)
			sol=m,dr=m-1;
	}
	
	printf("%lld",sol);
	return 0;
}