#include <fstream>
#include <vector>
#define i64 long long
#define xx 109547
#define pb push_back
#define szs(x) ((int)(x).size())

using namespace std;

i64 P, N;
vector < i64 > temp;

void frk (i64 B){
    int it;
    if ((B & 1) == 0){
        temp.pb(2);
        for (; (B & 1LL) == 0; B >>= 1);
    }
    for (it = 3 ; 1LL * it * it <= B; ++ it){
            if (B % it )
              continue;
            temp.pb(it);
            while (B % it == 0)
                  B /= it;
    }
    if (B > 1)
        temp.pb(B);
}

inline i64 pin (i64 A){
       i64 Ress = A;
       for (int mask = 1; mask < (1 << szs(temp)); ++ mask){
            i64 product = 1, sb = 0;
            for (int it = 0; it < szs(temp); ++ it){
                    if ((1 << it) & mask)
                       ++ sb, product *= temp[it];
            }
            sb = (sb & 1 ? -1 : 1);
            Ress += sb * A / product;
    }
    return Ress;
}

void doit (){
    frk(N);
    i64 st = 1, dr = (1LL * 1 << 61) | 1, Ress = -1;
    while (st <= dr){
            i64 mid = st + ((dr - st) >> 1);
            if (pin(mid) >= P)
               Ress = mid, dr = mid - 1;
            else st = mid + 1;
    }
    ofstream ("frac.out") << Ress;

}

int main(){
    ifstream ("frac.in") >> N >> P;
    doit();
    return 0;
}