#include<fstream>

using namespace std;

ifstream fin("zero2.in");
ofstream fout("zero2.out");

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(){
    for (int i=0;i<10;i++){
      fin>>N>>B;
      divizori(B);
      long long max=1000132;
         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";
    }

    return 0;
}