#include<fstream.h>
#include<values.h>
#include<math.h>
ifstream f("zero2.in");
ofstream g("zero2.out");
int main()
{long i,n,m,b,k,v[5000][3],j,d,e,h,x,c;
 for(i=1;i<=10;i++){k=0;m=-1;
 f>>n;f>>b;x=b;
 j=2;while(b!=1){e=1;
  for(d=2;d<=sqrt(j);d++){
   if(j%d==0) e=0;
   if(e==0) break;
  }
  if(e==1) {if(b%j==0){m++;v[m][0]=j;v[m][1]=0;v[m][2]=0;}
  while(b%j==0){v[m][1]++;b=b/j;}}
  j++;
 }
 for(h=n;h>=2;h--){b=h;
 j=2;while(b!=1 && j<=b){e=1;
  for(d=2;d<=sqrt(j);d++){
   if(j%d==0) e=0;
   if(e==0) break;
  }
  if(e==1 && x%j==0 && h%j==0){for(d=0;d<=m;d++) if(v[d][0]==j) break;
     e=h;c=0;b=b/j;do{e=e/j;c++;}while(e%j==0);
     v[d][2]=v[d][2]+(n-h+1)*c;}
  j++;
 }}
 d=MAXLONG;
 for(j=0;j<=m;j++){v[j][2]=v[j][2]/v[j][1];if(d>v[j][2])d=v[j][2];}
 k=k+d;
 if(i!=1) g<<endl; g<<k;}
 f.close();g.close();return 0;}