#include<fstream.h>
long a[1000],N,B,nr,nr1,b[1000];
void divizori(long B){
for (int t=0;t<nr;t++) {
   a[t]=0;
   b[t]=0;}
if (B%2==1)
nr=0;
while (B%2==0){
a[0]=2;
b[0]++;
B/=2;
nr=1;}
for (long d=3;d<=B/d;d+=2){
	if (B%d==0)
	  nr++;
     while (B%d==0){
     a[nr-1]=d;
     b[nr-1]++;
     B/=d;}             }
if (B!=1){
a[nr++]=B;
b[nr-1]=1;}
}
int main(){
ifstream fin("zero2.in");
ofstream fout("zero2.out");
for (int i=0;i<10;i++){
  fin>>N>>B;
  divizori(B);
  long max=1000132;
  for (int i=0;i<nr;i++){
     long u=a[i];
     nr1=0;
     while (u<=N){
	for (int t=2;t<=N;t++)
	   nr1+=t/u;
	u*=a[i];}
     if (nr1>=b[i]&&max/b[i]<=max)
	 max=nr1/b[i];
     if (max==0)
	break;
	}
     if (max==1000132)
     max=0;
     fout<<max<<"\n";
      }
fin.close();
fout.close();
return 0;
}