#include<fstream.h>
long long a[1000],N,B,nr,nr1,b[1000];
void divizori(long long B){
a[0]=0;
b[0]=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++;
	  a[nr-1]=0;
	  b[nr-1]=0;}
     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 long max=1000132;
 // for (int i=0;i<nr;i++){
     long long u=a[nr-1];
     nr1=0;
     while (u<=N){
	for (long t=2;t<=N;t++)
	   nr1+=t/u;
	u*=a[nr-1];}
     if (nr1>=b[nr-1]&&max/b[nr-1]<=max)
	 max=nr1/b[nr-1];
     if (max==0)
	break;  //}
     if (max==1000132)
     max=0;
     fout<<max<<"\n";
      }
fin.close();
fout.close();
return 0;
}