#include <iostream>
#include <fstream>
using namespace std;
const int L=25;
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 b=2;
    int pb=1;
    int i,pi;
    for(i=2;i<=x && x!=1 ;i++)
    {
        pi=0;
        while(x%i==0)
        {
            x=x/i;
            pi++;
        }
        if(factorial(i,pi)>factorial(b,pb))
        {
            b=i;
            pb=pi;
        }
    }
    a=b;
    pa=pb;
}

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;
}