#include<stdio.h>
#include<vector>
#define pb push_back
#define maxlen (1LL<<61)+1
using namespace std;
typedef long long ll;

ll n,p,nr,prod=1;
vector <ll> l;
int x[50];

void read()
{
    scanf("%lld%lld",&n,&p);
    ll nc=n;
    for(int i=2;i*i<=nc && nc>1;i++)
      if(nc%i==0)
      {
          l.pb(i);
          for(;nc%i==0 && nc>1;nc/=i);
      }
      if(nc>1) l.pb(nc);
}

void back(int k,int sgn,ll nc)
{
    if(k-1>0) nr+=sgn*(nc/prod);
    if(k>nc) return;
    for(unsigned int i=x[k-1]+1;i<l.size();i++)
    {
        x[k]=i;
        prod*=l[i];
        back(k+1,-sgn,nc);
        prod/=l[i];
    }
}

ll solve()
{
    ll i,step=maxlen,sol;

    x[0]=-1;
    for(i=-1;step;step>>=1)
     if(i+step<=maxlen)
     {
         prod=1; nr=0; back(1,-1,i+step);
         if(i+step-nr==p) sol=i+step;
         else
          if(i+step-nr<p) i+=step;
     }
     return sol;
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    read();
    printf("%lld",solve());

}