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

long long n, b, f, nr,min, fminim,contor, d[5000], p;
char u[5000];

void ciur()
{
  long i,j;
 memset(u,'0',sizeof(u));
  for (i=2; i<=5000; i++)
    {
      if (u[i]=='0') 
  	{
	  d[++p]=i;
	  j=2;
	  while (i*j<5000) u[i*(j++)]='1';
	}
    }
}

void div(long x)
{
  long i,r;
  for (i=1;d[i]*d[i]<=x && i<=p; i++)
    {
      r=0;
      while (x%d[i]==0)	r++,x/=d[i];
      fminim=d[i];
 	min=r;
    }
  if (x!=1) fminim=x, min=1;
  
}

long v[100],ex[100], minim=LONG_MAX, expmin;


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=3; i<=copy/3; i+=2)
    {
      if (copy%i==0)
	{
	  v[++nr]=i; ex[nr]=0;
	  while (copy%i==0)  {ex[nr]++; copy/=i;}
	}
    }
  if (copy) v[++nr]=copy, ex[nr]=1;
}

int nrz(long k)
{
  int i, j, cont;
  minim=LONG_MAX;
  cont=0; j=1;
      while (pow(fminim,j)<=k)	{ cont+=(k/pow(fminim,j)); j++;}
      if (cont<minim) minim=cont, expmin=min;
   
  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);
     div(b);
     for (i=2; i<=n; i++)contor+=nrz(i);
     printf("%ld\n",contor/expmin);
   }
  return 0;
}