#include <fstream.h>
#define max 48000

long p, q, baza[max], dim, bazaf[max], expf[max], dimf;
long exp[max];

void desc(long baza[max], long exp[max], long p, long q, long &dim)
{
	long i, d=2;
	while (p!=1)
		{
		  if (p%d==0)
			{for (i=0; i<dim; i++) if (baza[i]==d) break;
			baza[i]=d;
			while (p%d==0)
				{p/=d; exp[i]++;}
			exp[i]*=q;
			if (i==dim) dim++;
			}
		d++;

		}
}

int ok ()
{
	long i, j, aux;
	for (i=0; i<dim; i++)
		{aux=0;
		for (j=0; j<dimf; j++)
			if (exp[i]==expf[j] && baza[i]==bazaf[j])
				aux=1;
			if (!aux) return 0;
		}
	return 1;
}



int main()
{
	long i;
	ifstream f("gfact.in");
	ofstream g("gfact.out");
	f>>p>>q;
	f.close();
	if (p==1) g<<"0\n";
	else {
	desc(baza, exp, p, q, dim);
	/*if (dim==1) g<<baza[0]<<"\n";
	else*/
	{
	i=2;
	while (1)
		{
		  desc (bazaf, expf, i, 1, dimf);
		  if (ok()) {g<<i<<"\n"; break; }
		  i++;
		}
	}}
	g.close();
	return 0;
}