#include <iostream>
#include <fstream>
#include <vector>

#define int long long

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

vector <int> factori;

int pop_count(int mask){
    int ans = 0;
    while(mask) ans += (mask & 1), mask >>= 1;
    return ans;
}

int pinex(int a, int b){
    int ans = 0;
    for(int mask = 0; mask < (1 << (int)factori.size()); mask++){
        int prod = 1, cmask = mask, i = 0;
        while(cmask){
            if(cmask & 1) prod *= factori[i];
            cmask >>= 1, i++;
        }
        pop_count(mask) % 2 == 0 ? ans += (a / prod) : ans -= (a / prod);
    }
    return ans;
}

signed main(){
    int n, p;
    fin >> n >> p;
    int b = n;
    int div = 2;
    while(div * div <= b){
        if(b % div == 0){
            factori.push_back(div);
            while(b % div == 0) b /= div;
        }
    }
    if(b > 1) factori.push_back(b);
    int st = 1, dr = (1ll << 61), ans = -1;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(pinex(mij, n) >= p) dr = mij - 1, ans = mij;
        else st = mij + 1;
    }
    fout << ans;
    return 0;
}