#include <fstream>
#define ull unsigned long long
#include <vector>

using namespace std;

ifstream cin ("frac.in");
ofstream cout ("frac.out");

ull n, p;

vector <int> d;

void desc ()
{
    int d1 = 2;
    while (d1 * d1 <= n)
    {
        if (!(n % d1))
        {
            while (!(n % d1))
                n /= d1;
            d.push_back(d1);

        }
        ++d1;
    }
    if (n > 1)
    {
        d.push_back(n);
    }
}
int pinex (int x)
{
    int sum = x;
    int l = d.size();
    for (int i = 1; i < (1 << l); ++i)
    {
        int nr = 0;
        int prod = 1;
        for (int j = 0; j < l; ++j)
            if (i & (1 << j))
            {
                ++nr;
                prod *= d[j];
            }
        (nr & 1) ? sum -= x / prod : sum += x / prod;
    }
    return sum;
}
int cb (int st, int dr)
{
    int med, last = -1;
    while (st <= dr)
    {
        med = (st + dr) >> 1;
        if (pinex(med) == p)
        {
            last = med;
            dr = med - 1;

        }
        else if (pinex(med) > p)
            dr = med - 1;
        else
            st = med + 1;
    }
    return last;
}
int main()
{
    cin >> n >> p;
    desc();
    ull o = 1e14;
    cout << cb (1, o) << '\n';

    return 0;
}