#include<stdio.h>
#include<fstream.h>
#include<math.h>
#define nmax 10000
#define tip unsigned long long
tip prim[nmax],numar[nmax];
tip rezolva(tip,tip); void desc(tip);tip s(tip,tip);


int main()
 {tip i;
  tip a,b;
 freopen("zero2.in","r",stdin);
 freopen("zero2.out","w",stdout);

 for(i=1;i<=10;i++)
   {scanf("%llu%llu",&a,&b);
	printf("%llu\n",rezolva(a,b));
	}
 fclose(stdout);
 return 0;
 }

tip rezolva(tip n,tip b)
{tip nr[nmax],i,min,p;
 memset(nr,0,sizeof(nr));
 desc(b);

 for(i=1;i<=prim[0];i++)
  {for(p=prim[i];p<=n;p*=prim[i])
	 nr[i]+=s(n,p);
   nr[i]/=numar[i];
   }
 for(i=2,min=nr[1];i<=prim[0];i++)
  if(nr[i]<min)
   min=nr[i];
  return min;
  }

tip s(tip n,tip p)
{tip k;
 k=n/p-1;
 return (k+1)*(n-(k+1)*p+1)+(k+1)*k*p/2;
 }

void desc(tip x)
{tip d;
 memset(prim,0,sizeof(prim));
 memset(numar,0,sizeof(numar));

 for(d=2;d<=sqrt(x);d++)
   if(!(x%d))
	 {prim[++prim[0]]=d;
	  while(!(x%d))
		{x/=d;
		 numar[prim[0]]++;
		 }
	 }
 if(x>1)
  {prim[++prim[0]]=x;
   numar[prim[0]]++;
   }
}