#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=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(v[nr],j)<=k)	{ cont+=(k/pow(v[nr],j)); j++;}
      if (cont<minim) minim=cont, expmin=ex[nr];
   
  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);
     for (i=2; i<=n; i++)contor+=nrz(i);
     printf("%ld\n",contor/expmin);
   }
  return 0;
}