#include <iostream>
#include <fstream>
using namespace std;
const int L=30;
long long a,pa;
long long numarp(long long x,long long p)
{
    long long nrp=0;
    while(x!=0)
    {
        nrp=nrp+x/p;
        x=x/p;
    }
    return nrp;
}
long long factorial(long long x,long long p)
{
    long long pas,r;
    r=0;
    pas=1<<L;
    while(pas!=0)
    {
        if(numarp(r+pas,x)<p)
            r=r+pas;
        pas=pas/2;
    }
    return r;
}
void factdominant(long long x, long long &a, long long &pa)
{
    long long i=2,pi,k=0,k2;
    while(i*i<=x)
    {
        if(x%i==0)
        {
            pi=0;
            while(x%i==0)
            {
                x=x/i;
                pi++;
            }
            k2=factorial(i,pi);
            if(k2>k)
            {
                k=k2;
                a=i;
                pa=pi;
            }
        }
        i++;
    }
    if(x!=1 && k<factorial(x,1))
    {
        a=x;
        pa=1;
    }
}

int main()
{
    long long p,q,r;
    long long pas;
    ifstream f("gfact.in");
    ofstream g("gfact.out");
    f>>p>>q;
    factdominant(p,a,pa);
    p=a;
    q=q*pa;
    r=0;
    pas=1<<L;
    while(pas!=0)
    {
        if(numarp(r+pas,p)<q)
            r=r+pas;
        pas=pas/2;
    }
    r++;
    g<<r;
    return 0;
}