#include <iostream>

using namespace std;

long long n,p,st,dr,i,j,div[500],nr;

void descompunere(long long n)
{
    if (n%2==0)
        div[++nr]=2;
    while (n%2==0)
        n/=2;
    i=3;
    while (n>1)
    {
        if (n%i==0)
        {
            div[++nr]=i;
            while (n%i==0&&n>1)
                n/=i;
        }
        i+=2;
    }
}

long long ans(long long m)
{
    long long rez=m;
    for (i=1; i<=nr; i++)
        rez=rez-m/div[i];
    long long pow=(1<<nr)-1;
    for (i=3; i<=pow; i++)
    {
        int nrbiti=0;
        long long ci=i;
        while (ci>0)
        {
            if (ci%2==1)
                nrbiti++;
            ci/=2;
        }
        if (nrbiti>1)
        {
            long long aux=m;
            for (j=1; j<=nr; j++)
            {
                if ((1<<(j-1)&i)>0)
                    aux/=div[j];
            }
            rez+=aux;
        }
    }
    return rez;
}

void afisare(long long k)
{
    while (ans(k)==p)
        k--;
    cout << k+1 << '\n';
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    cin >> n >> p;
    descompunere(n);
    st=1;
    dr=100000000000000;
    while (st<=dr)
    {
        long long m=(st+dr)/2;
        long long k=ans(m);
        if (k==p)
        {
            afisare(m);
            return 0;
        }
        if (ans(m)>p)
            dr=m-1;
        else
            st=m+1;
    }
}