#include <cstdio>

int main(){
    FILE*fi,*fout;
    int i,e,exp;
    long long n,b,maxdiv,d,x,s,p;
    fi=fopen("zero2.in" ,"r");
    fout=fopen("zero2.out" ,"w");
    for(i=0;i<10;i++){
        fscanf(fi,"%lld%lld" ,&n,&b);
        d=2;
        maxdiv=0;
        while(d*d<=b){
            e=0;
            p=1;
            while(b%d==0){
                b/=d;
                p*=d;
                e++;
            }
            if(e>0&&maxdiv<p){
               maxdiv=d;
               exp=e;
            }
            d++;
        }
        if(maxdiv<b){
           maxdiv=b;
           exp=1;
        }
        x=maxdiv;
        s=0;
        while(maxdiv<=n){
             s=s+maxdiv*((n/maxdiv)*(n/maxdiv-1))/2+(n+1-(n/maxdiv)*maxdiv)*(n/maxdiv);
             maxdiv*=x;
        }
        fprintf(fout,"%lld\n" ,s/exp);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}