#include <stdio.h>
#include <bitset>
using namespace std;

long pr[15000],q;
bitset <40005>prim;
long t,n,b,i,j;
long long k,x[100],p[100],r,nr,s[100],rap;
 
int main(){
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    //numere prime
    q=1;
    pr[1]=2;
    for (i=3;i<=40000;i+=2)
        if (!prim[i]){
           pr[++q]=i;
           for (j=3*i;j<=40000;j+=i+i)
               prim[j]=1;
        }
    //calculare 
    for (t=10;t;--t){
        scanf("%ld %ld",&n,&b);

        nr=0;i=1;
        while (pr[i]*pr[i]<=b){
              if (b%pr[i]==0){
                 nr++;
                 x[nr]=pr[i];
                 p[nr]=1;
                 b/=pr[i];
                 while (b%pr[i]==0){p[nr]++;b/=pr[i];}
              }
              i++;
        }
        if(b!=1){nr++;x[nr]=b;p[nr]=1;}

        for (i=1;i<=nr;i++){
            j=1;s[i]=0;
            r=1;
            while (n/r>=x[i]){
                  r*=x[i];
                  k=n/r-1;
                  s[i]+=(long long)k*(k+1)/2*r+(k+1)*(n-(k+1)*r+1);
            }
        }
        //for (i=1;i<=nr;i++)fprintf(f2,"* %ld *",x[i]);   
        rap=s[1]/p[1];
        for (i=1;i<=nr;i++)
            if (s[i]/p[i]<rap)rap=(long long)s[i]/p[i];
        printf("%lld\n",rap);   
    }

return 0;
}