#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
FILE*in=fopen("frac.in","r");
FILE*out=fopen("frac.out","w");
int it=1,i;
long long prim[1007],INF;
bool b[1007];
long long n,p,m;
long long hm(long long x)
{
    long long s=0,j,onect,prod,term,ra;
    memset(b,0,sizeof(b));
    while(true)
    {
        j=1;
        while(b[j]==1)
        {
            b[j]=0;
            j++;
        }
        if(j==it)
        {
            ra=(long long)(x-s);
            return ra;
        }
        b[j]=1;
        onect=0;
        prod=1;
        for(j=1;j<it;j++)
        {
            if(b[j]==1)
            {
                onect++;
                prod=(long long)(prod*prim[j]);
            }
        }
        int t;
        if(onect%2==1)
        {
            t=1;
        }
        else
        {
            t=-1;
        }
        term=(long long)(x/prod);
        term=(long long)(t*term);
        s=(long long)(s+term);
    }// cel mai din stanga cu hm(a)==p
}
long long bs()
{
    long long st=1,dr=INF,mij,ras;
    while(st<=dr)
    {
        mij=(long long)(((long long)(st+dr))/2);
        if(hm(mij)<p)
        {
            st=(long long)(mij+1);
        }
        if(hm(mij)>p)
        {
            dr=(long long)(mij-1);
        }
        if(hm(mij)==p)
        {
            ras=(long long)(mij);
            dr=mij-1;
        }
    }
    return ras;
}
int main()
{
    fscanf(in,"%lld%lld",&n,&p);
    m=(long long)(n);
    if(n==1)
    {
        fprintf(out,"%lld",p);
        return 0;
    }
    for(i=2;i<=sqrt(m);i++)
    {
        if(n%i==0)
        {
            prim[it]=i;
            it++;
            n=(long long)(n/i);
        }
        while(n%i==0)
        {
            n=(long long)(n/i);
        }
        if(n==1)
        {
            break;
        }
    }
    if(n!=1)
    {
        prim[it]=n;
        it++;
    }
    INF=1;
    for(i=1;i<=61;i++)
    {
        INF=(long long)(INF*2);
    }
    fprintf(out,"%lld",bs());
}