#include <stdio.h>
#define Nr_pmax 100000 // 10^5
#define MM 100
#define ll long long 

ll n,p,z,rez,INF;
ll v[MM];

void pre_work(){
	ll i;
	if(n%2==0){
   	while(n %2==0) n/=2;
      v[++v[0]]=2;
   }
   for(i=3;i*i<=n;i+=2)
   	if(n % i==0){
      	while(n%i==0) n/=i;
         v[++v[0]]=i;
      }
   if(n>1) v[++v[0]]=n;
}
ll work(ll m){
	ll sum,i,j,prod,nr;
   sum=0;
   for(i=1; i<(1<<v[0]); i++){
   	prod=1; nr=0;
      for(j=0;j<v[0];j++)
      	if(i & (1<<j)){
         	nr++;
         	prod *= v[j+1];
         }
      if(nr %2) sum += m/prod;
      else sum -= m/prod;
   }
   return m-sum;
}

ll caut_bin(ll l,ll r){
	ll m,rez=-1,x;
   while(l <= r){
   	m=l+(r-l)/2;
      x=work(m);
      if(x==p) {rez=m; r=m-1;}
      else
      if(x>p) r=m-1;
      else l=m+1;
   }
   return rez;
}

int main(){
	freopen("frac.in","r",stdin);
   freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);

   pre_work();

   INF = 1LL<<61;
   rez = caut_bin(1,INF);

   printf("%lld\n",rez);
   fclose(stdin); fclose(stdout);
   return 0;
}