#include<cstdio>
long long n,b,i,j,d[100050],p[100050],pt[100050],v[100050],m,nr,k,x,nrr,a,nmin;
FILE *f,*g;
int main(){
    f=fopen("zero2.in","r");
    g=fopen("zero2.out","w");
    for(k=1;k<=10;k++){
        fscanf(f,"%lld%lld",&n,&b);
        nr=0;
        a=b;
        nmin=1LL<<62;
        for(i=2;i<=b/i;i++){
            if(a%i==0){
                d[++nr]=i;
                p[nr]=0;
                while(a%i==0){
                    p[nr]++;
                    a/=i;
                }
            }
        }
        if(a!=1){
            d[++nr]=a;
            p[nr]=1;
        }
        for(i=1;i<=nr;i++){
            x=0;
            for(j=d[i];j<=n;j*=d[i]){
                a=n/j;
                a=j*a*(a-1)/2+(n+1-a*j)*a;
                x+=a;
            }
            x/=p[i];
            if(x<nmin)
                nmin=x;
        }
        fprintf(g,"%lld\n",nmin);
    }








    fclose(f);
    fclose(g);
    return 0;
}