#include <fstream>

using namespace std;
ifstream fin("gfact.in");
ofstream fout("gfact.out");
const int L=45;
const int ND=10;
int d[ND],e[ND],nd,p,q;
void desc(int n)
{
    int i=2;
    while(i*i<=n)
    {
        if(n%i==0)
        {
            d[nd]=i;
            while(n%i==0)
                {
                    e[nd]++;
                    n/=i;
                }
             nd++;
        }
        i++;
    }
    if(n!=1)
    {
        d[nd]=n;
        e[nd]=1;
        nd++;
    }
}
long long  putere(long long n,int x)
{
    long long  nr=0;
    while(n>=x)
    {
        nr+=n/x;
        n/=x;
    }
return nr;
}
bool divizibil(long long  n)
{
    //verifica daca n e divizibil cu p^q;
    for(int i=0;i<nd;i++)
        if(putere(n,d[i])<e[i]*q)
          return false;
    return true;
}

int main()
{
    long long pas,r;
    pas=1LL<<L;
    r=0;
    fin>>p>>q;
    desc(p);
    while(pas!=0)
    {
        if(divizibil(r+pas)==false)
            r+=pas;
        pas/=2;
    }
    r++;
    fout<<r;
    return 0;
}