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

#define int long long

using namespace std;

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

void decomp(int n, vector <int> &fact){
    int div = 2;
    while(div * div <= n){
        if(n % div == 0){
            fact.push_back(div);
            while(n % div == 0) n /= div;
        }
        div++;
    }
    if(n != 1) fact.push_back(div);
}

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

vector <int> fact;
int pinex(int a, int b){
    int ans = 0;
    for(int mask = 0; mask < (1 << (int)fact.size()); mask++){
        int prod = 1, i = 0, cmask = mask;
        while(cmask){
            if(cmask & 1) prod *= fact[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, decomp(n, fact);
    int st = 1, dr = (1ll << 61), ans = -1;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(pinex(mij, n) >= p) dr = mij - 1, ans = mij;
        else st = mij + 1;
    }
    fout << ans;
    return 0;
}