#include <iostream>
#include <fstream>
using namespace std;
const int L=31;
unsigned long long a,pa;
unsigned long long numarp(unsigned long long x,unsigned long long p)
{
    unsigned long long nrp=0;
    while(x!=0)
    {
        nrp=nrp+x/p;
        x=x/p;
    }
    return nrp;
}
unsigned long long factorial(unsigned long long x,unsigned long long p)
{
    unsigned 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(unsigned long long x, unsigned long long &a, unsigned long long &pa)
{
    unsigned long long i=2,pi,k=0,k2;
    while(x!=1)
    {
        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++;
    }
}

int main()
{
    unsigned long long p,q,r;
    unsigned 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;
}