# include <stdio.h>
# include <math.h>

# define MAXP 7000


long int ciur[MAXP+1],ciurlen,p,q;
long int fact[MAXP+1],factlen,rep[MAXP+1];
long int solp[MAXP+1],sol;

long int max(long int a, long int b) {if (a>b) return a; return b;}

void citire()
{
     FILE *f=fopen("gfact.in","r");
     fscanf(f,"%ld%ld",&p,&q);
     fclose(f);
}

long int prim(long int a)
{
     long int i;
     for (i=1;i<=ciurlen&&ciur[i]*ciur[i]<=a;i++)
         if (a%ciur[i]==0) return 0;
     return 1;
}

void make_ciur()
{
     long int i,upper_bound=(long int)sqrt(p)+1;
     ciur[1]=2;
     ciurlen=1;
     for (i=3;i<=upper_bound;i+=2)
         if (prim(i)) ciur[++ciurlen]=i;
}

void factorizeaza_p()
{
     long int i;
     for (i=1;p!=1;i++)
         {
         if (p%ciur[i]==0)
            {
            fact[++factlen]=ciur[i];
            rep[factlen]=0;
            while (p%ciur[i]==0) 
                  {
                  p/=ciur[i];
                  rep[factlen]++;
                  }
            }
         if (p!=1&&ciur[i]*ciur[i]>p)
            {
            fact[++factlen]=p;
            rep[factlen]=1;
            break;
            }
         }
}
           
void inmulteste_rep_q()
{
     long int i;
     for (i=1;i<=factlen;i++) rep[i]*=q;
}

long int puterea(long int x, long int p)
{
     long int sol=0;
     while (x) {sol+=x/p;x/=p;}
     return sol;
}

long int searchbin(long int li, long int lf, long int target, long int base)
{
     //printf("%ld:%ld:%=%d\n",li,lf,target);
     if (li>lf) return 0;
     long int m=(li+lf)/2;
     long int pm=puterea(m,base),pm1=puterea(m-1,base);
     if (pm>=target&&pm1<target) return m;
     if (pm<target) return searchbin(m+1,lf,target,base);
     return searchbin (li,m-1,target,base);
}

void calculeaza()
{
     long int i;
     for (i=1;i<=factlen;i++) //pt fiecare factor prim
         {
         if (rep[i]<=fact[i]) solp[i]=fact[i]*rep[i];
         else solp[i]=searchbin(1,fact[i]*rep[i],rep[i],fact[i]);
         }
     //getchar();
}

void scrie_fisier(long int sol)
{
     FILE *g=fopen("gfact.out","w");
     fprintf(g,"%ld\n",sol);
     fclose(g);
}

void get_solution()
{
     sol=solp[1];
     long int i;
     for (i=2;i<=factlen;i++)
         sol=max(sol,solp[i]);
}

int main()
{
    citire();
    make_ciur();
    factorizeaza_p();
    inmulteste_rep_q();
    calculeaza();
    get_solution();
    scrie_fisier(sol);
    //getchar();
    return 0;
}