#include <cstdio>
#include <vector>

using namespace std;

vector <int> prime;
vector <long long> fact;
bool c[1000005];

void ciur() {
    int n = 1000000, radmax = 1000;
    prime.push_back(2);
    for(int i = 3; i <= radmax; i += 2)
        if(!c[i])
            for(int j = i * i; j <= n; j += 2 * i)
                c[j] = 1;
    for(int i = 3; i <= n; i += 2)
        if(!c[i])
            prime.push_back(i);
}

void descompunere(long long n) {
    int ind = 0, e;
    fact.clear();
    while(ind < prime.size() && n > 1 && (long long)prime[ind] * prime[ind] <= n) {
        e = 0;
        while(n % prime[ind] == 0) {
            n /= prime[ind];
            ++ e;
        }
        if(e > 0) {
            fact.push_back(prime[ind]);
        }
        ++ ind;
    }
    if(n > 1) {
        fact.push_back(n);
    }
}

long long pinex(long long a) {
    int semn;
    long long submultimi, factor, rasp = 0;
    submultimi = 1LL << fact.size();
    for(long long i = 1; i < submultimi; ++ i) {
        semn = 0;
        factor = 1;
        for(int j = 0; j < fact.size(); ++ j) {
            if(((1LL << j) & i) != 0) {
                semn = (semn + 1) % 2;
                factor *= fact[j];
            }
        }
        if(semn % 2 == 0) {
            rasp = rasp - a / factor;
        } else {
            rasp = rasp + a / factor;
        }
    }
    return a - rasp;
}

void cautbinar(long long val) {
    long long st = 1, dr = 1LL << 61, med, last = -1;
    while(st <= dr) {
        med = st + (dr - st) / 2;
        if(pinex(med) >= val) {
            last = med;
            dr = med - 1;
        } else {
            st = med + 1;
        }
    }
    printf("%lld\n", last);
}

int main() {
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);

    ciur();
    long long n, p;
    scanf("%lld%lld", &n, &p);
    descompunere(n);
    cautbinar(p);

    return 0;
}