#include <stdio.h>
#include <math.h>

int main(){
    FILE *f1,*f2;
    f1=fopen("zero2.in","r");
    f2=fopen("zero2.out","w");
    long pr[20000];
    long long n,b,i,j,t,ok,q,x[100],p[100],r,nr,s[100],rap;
    double g;
    pr[1]=2;pr[2]=3;
    q=2;
    i=3;
    while (i<31630){
          do{
             i+=2;
               ok=1;
               j=1;
               while (pr[j]*pr[j]<=i){
                     if (i%pr[j]==0){ok=0;break;}
                     j++;
               }
          }while (ok==0);
          q++;
          pr[q]=i;
    }
    t=10;
    for (;t>0;t--){
        fscanf(f1,"%ld",&n);
        fscanf(f1,"%ld",&b);
        nr=0;i=1;
        while (b>1){
              if (b%pr[i]==0){
                 nr++;
                 x[nr]=pr[i];
                 p[nr]=1;
                 b=b/pr[i];
                 while (b%pr[i]==0){p[nr]++;b=b/pr[i];}
              }
              else if(pr[i]*pr[i]>b){nr++;x[nr]=b;p[nr]=1;b=1;}
              i++;
              //fprintf(f2,"gfg");
        }
        //fprintf(f2,"gfg");
        for (i=1;i<=nr;i++){
            j=1;s[i]=0;
            r=x[i];
            while (r<=n){
                 g=(double)(n-r+1)/r;
                 s[i]+=r*((long)g)*((long)g+1)/2;
                 //fprintf(f2,"%ld ",s[i]);
                 s[i]+=(g-(long)g)*((long)g+1)*r;
                 //fprintf(f2,"*%ld\n",s[i]);
                 r*=x[i];
            }
        }
        //for (i=1;i<=nr;i++)fprintf(f2,"* %ld *",x[i]);
        rap=pow(10,19);
        for (i=1;i<=nr;i++)if (s[i]/p[i]<rap)rap=(long long)s[i]/p[i];
        fprintf(f2,"%lld\n",rap);
    }
    fclose(f1);
    fclose(f2);
    return 0;
}