#include <iostream>
#include <fstream>
using namespace std;
const int L=30;
int a,pa;
int numarp(long long x,int p)
{
    int nrp=0;
    while(x!=0)
    {
        nrp=nrp+x/p;
        x=x/p;
    }
    return nrp;
}
int factorial(int x,int p)
{
    int r;
    long long pas;
    r=0;
    pas=1<<L;
    while(pas!=0)
    {
        if(numarp(r+pas,x)<p)
            r=r+pas;
        pas=pas/2;
    }
    return r;
}
void factdominant(int x, int &a, int &pa)
{
    int 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(pa==1)
        a=x;
}

int main()
{
    int 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;
}