#include<stdio.h>

long n, b, f, nr, ex;

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

void descomp(long x)
{
  long y=x;
  if (y%2==0)
    {
      f=2;ex=0;
      while (y%2==0) { y/=2; ex++;}

    }
  for (long i=3; i<=y; i++)
    {
      if (y%i==0)
	if (prim(i))
	  {
	    ex=0;
	    f=i;
	    while (y%i==0) { y/=i; ex++;}

	  }
    }
}

int main()
{
  freopen("zero2.in","r",stdin);
  freopen("zero2.out","w",stdout);
  long nr, contor=0;
  for (int z=1; z<=10; z++)
    {
      scanf("%ld %ld",&n, &b);
      descomp(b);
      contor=0;
      nr=f;
      long d=f;
      nr=f;
      while (nr<=d)
	{
	  long p=nr;
	  while (p%f==0) { contor++; p/=f;}
	  nr+=f;
	}
      for (d=f+1; d<=n; d++)
	{
	  long p=d;
	  while (p%f==0){contor++; p/=f;}
	}

      printf("%ld\n",contor/ex);
    }
  return 0;
}