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

long long n, b, f, nr, ex, min, fminim;

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

void descomp(long long x)
{
  long long y=x; min=x;
  if (y%2==0)
    {
      f=2;ex=0;
      while (y%2==0) { y/=2; ex++;}
      min=ex;
      fminim=2;
    }
  for (long long i=3; i<=y; i++)
    {
      if (y%i==0)
	if (prim(i))
	  {
	    ex=0;
	    f=i;
	    while (y%i==0) { y/=i; ex++;}
	    if (min>=ex)	 {min=ex; fminim=f;}
	  }
    }
}

long long nrz(long long x)
{
  long long p=1, contor=0;
  while (pow(fminim,p)<=x) contor+=(x/pow(fminim,p++));
  return contor;
}

int main()
{
  long long i,z;
  freopen("zero2.in","r",stdin);
  freopen("zero2.out","w",stdout);
  long long nr, contor=0;
  for (z=1; z<=10; z++)
    {
      scanf("%lld %lld",&n, &b);
      if (!prim(b)) descomp(b);
	else fminim=b;
      contor=0;
      for (i=1; i<=n; i++) contor+=nrz(i);
      printf("%lld\n",contor/min);
    }
  return 0;
}