#include <fstream>
#include <map>
using namespace std;
map<long long,long long>puteri;
ifstream in("gfact.in");
ofstream out("gfact.out");
void descompunere(long long n,long long p){
    long long d=2;
    while(d*d<=n){
        if(n%d==0){
            puteri[d]=0;
            while(n%d==0)
                n/=d,puteri[d]++;
            puteri[d]*=p;
        }
        d++;
    }
    if(n>1)
        puteri[n]=p;
}
long long legendre(long long n ,long long d){
  long long rasp=0;
  while(d<=n){
    rasp+=(n/=d);
  }
  return rasp;
}
bool verif(long long l){
    for(auto it=puteri.begin();it!=puteri.end();it++){
        if(legendre(l,(*it).first) >= (*it).second)
            return 1;
    }
    return 0;
}
long long cbin(){
    long long pas=(1LL)<<60 ,d=0;
    while(pas>0){
        if(!verif(pas+d)){
            d+=pas;
        }
        pas/=2;
    }
    return d+1;
}
int main()
{
    long long p,q;
    in>>p>>q;
    descompunere(p,q);
    out<<cbin();
    return 0;
}