#include <stdio.h>
#include <values.h>
#include <string.h>
#include <math.h>
#define X 20
#define LL long long
// E(n) = 1! * 2! * ... *n!
// Nr(n,p) = puterea la care apare p in E(n)
// S(n,p) = [n / p] + [(n-1)/p] + .. + [1/p]
// Nr(n,p) = S(n,p) + S(n,p^2) + ..

int n,B,t;
int p[X],e[X],z;

void factorizez(int B){
	int i; z=0;
   memset(e,0,sizeof(e));
   if( B % 2 == 0){
   	p[++z]=2;
      while(B % 2 ==0) B /=2, e[z]++;
   }
   for(i=3; i<=sqrt(B); i+=2)
   if( B % i == 0){
   	p[++z]=i;
      while(B % i ==0) B /=i, e[z]++;
   }
   if(B>1) p[++z]=B, e[z]=1;
}

void solve(int n,int B){
	int i,k; LL pr,nr,min;
    min = MAXINT;
   factorizez(B);
   for(i=1; i<=z; ++i){ // pt fiecare factor prim
   	nr =0;
      for(pr=p[i];  n/pr > 0; pr *=p[i] ){
      	k = n/pr -1;
      	nr += k*(k+1)/2 *pr + (k+1)*(n-(k+1)*pr +1);
      }
      if( nr / e[i] < min) min=nr/e[i];
   }

   printf("%lld\n",min);
}

int main(){
	freopen("zero2.in","r",stdin);
   freopen("zero2.out","w",stdout);
   for(t=10; t; --t){
   	scanf("%d%d",&n,&B);
      solve(n,B);
   }

   fclose(stdin); fclose(stdout);
   return 0;
}