#include <bits/stdc++.h>
using namespace std;

ifstream f("gfact.in");
ofstream g("gfact.out");

const int nmax=5000005;
long long int i,p,q,divizor,put,factmax,nrprim,boss,added;
long long int primes[nmax],fr[nmax];

bool prim()
{
    long long int h;
    for (h=2;h*h<=p;h++)
     if (p%h==0)
      return 0;
    return 1;
}

bool descompunere (long long int numar , long long int necesar ,long long int ori)
{
    long long int imp,powsofar,current=1;
    powsofar=0;
    while (powsofar<necesar && current<=numar/ori)
    {
        current*=ori;
        powsofar+=(numar/current);
    }

    if (powsofar>=necesar)
     return 1;
   return 0;
}

long long int bin_search (long long int x)
{
    long long int st,dr,numar,mij,lastp=-1,aux;
    st=0;
    dr=2000000000;

    while (st<=dr)
    {
        mij=(st+dr)/2;
        numar=mij;
        aux=descompunere(numar,fr[x],primes[x]);
        if (aux)
        {
            lastp=numar;
            dr=mij-1;
        }
        else
           st=mij+1;
    }
    if (lastp>0) return lastp;
    return -1;
}

int main()
{
    f>>p>>q;
    divizor=2;

    if (p==1)
    {
        g<<1;
        return 0;
    }

    if (prim())
    {
        added=0;
        primes[++nrprim]=p;
        fr[nrprim]=p*q;
    }

    while (p>1 && added==0)
    {
        put=0;
        while (p%divizor==0)
        {
            p/=divizor;
            put++;
        }
        if (put>0)
        {
            primes[++nrprim]=divizor;
            fr[nrprim]=put*q;
        }
        if (divizor>=3)
         divizor+=2;
        else
         divizor++;
    }

    for (i=1;i<=nrprim;i++)
    {
        boss=bin_search(i);
        if (boss>factmax)
         factmax=boss;
    }

    g<<factmax;
    return 0;
}