#include <fstream>
#include<vector>
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
#define int long long
vector<int> prm(int n)
{
    vector<int> prime;
    for (int d=2; d*d<=n; d++)
    {
        if (n % d == 0)
        {
            prime.push_back(d);
            while (n%d==0)
                n/=d;
        }
    }
    if (n>1)
    {
        prime.push_back(n);
    }
    return prime;
}
int coprime(int x, const vector<int>& primes)
{
    int sz=primes.size();
    int total=0;
    for (int mask=1; mask <(1<<sz); mask++)
    {
        int mult=1;
        int bits = 0;
        for (int i=0; i<sz; i++)
        {
            if (mask & (1<<i))
            {
                mult*=primes[i];
                bits++;
            }
        }
        if (mult>x)
        {
            continue;
        }
        int contrib = x/mult;
        if (bits%2==1)
        {
            total+=contrib;
        }
        else
        {
            total-=contrib;
        }
    }
    return x-total;
}
signed main()
{
    int n,p;
    in>>n>>p;
    vector<int> prim=prm(n);
    int l=1,r=1e15,ans=-1;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        int cop=coprime(mid,prim);
        if(cop<p)
        {
            l=mid+1;
        }
        else {
        ans=mid;
        r=mid-1;
        }
    }
    out<<ans;
    return 0;
}