#include<stdio.h>
#include<math.h>
#include<limits.h>

long n,b,v[100],ex[100],nr, contor, minim=LONG_MAX, expmin;

int prim(long x)
{
  long i;
  if (x==0 || x==1) return 0;
  if (x==2) return 1;
  for (i=3; i*i<=x; i+=2)
    if (x%i==0) return 0;
   return 1;
}

void descomp(long x)
{
  long copy=x, i;
  nr=0;
  if (copy%2==0) 
    {
      v[++nr]=2; ex[nr]=0;
      while (copy%2==0) {ex[nr]++; copy/=2;}
    }
  for (i=2; i<=copy; i++)
    {
      if (copy%i==0)
	{
	  v[++nr]=i; ex[nr]=0;
	  while (copy%i==0)  {ex[nr]++; copy/=i;}
	}
    }
}

int nrz()
{
  int i, j, cont;
  for (i=1; i<=nr; i++)
    {
      cont=0;
      for (j=1; j<=ex[i]; j++)
	{ cont+=(n/pow(v[i],j)); if (n/pow(v[i],j)==0) break;}
      if (cont<minim) minim=cont, expmin=ex[i];
    }
  return minim;
}
      
        

int main()
{
  long z,i,j;
  freopen("zero2.in","r",stdin);
  freopen("zero2.out","w",stdout);
  for (z=1; z<=10; z++)
   {
     contor=0;
     scanf("%ld %ld",&n,&b);
     descomp(b);
     contor=nrz();
     printf("%ld\n",contor/expmin);
   }
  return 0;
}