#include<fstream>
#include<vector>
using namespace std;
#define ll long long


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

ll solve(ll a, ll b) {
    ll d = 2, len = 0, res = 0;
    vector<ll> v;

    while (b > 1) {
        if (b % d == 0) {
            v.push_back(d);
            len++;
            while (b % d == 0) {
                b /= d;
            }
        }
        if (d * d > b) {
            if (b == 1)
                break;
            v.push_back(b);
            len++;
            b = 1;
        }
        else {
            d++;
        }
    }

    ll pw = ((ll)1 << len);
    ll nr;
    for (nr = 1; nr < pw; nr++) {
        ll pt = 1, cnt = 0;
        for (ll i = 0; i < len; i++) {
            if (nr & (1 << i)) {
                pt *= v[i];
                cnt++;
            }
        }
        if (cnt % 2 == 0)
            res -= a / pt;
        else
            res += a / pt;
    }

    return a - res;
}


int main() {
    ll n, p;
    ll l = 0, r = (1<<61),m,nr= (1 << 61);

    //cout << solve(13, 12);

    cin >> n >> p;

    

    while (l <= r) {
        m = (l + r) / 2;
        ll res = solve(m, n);
        if (res == p) {
            if (m < nr) {
                nr = m;
                r = m - 1;
            }
        }
        else if (res < p) {
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }

    cout << nr;

    return 0;
}