#include <cstdio>
inline long long gauss(long long n){
    return n*(n+1)/2;
}
inline int apar(int n, int x){
    long long s=0, e=x;
    while(e<=n){
        s+=e*gauss(n/e-1)+(n%e+1)*(long long)(n/e);
        e*=x;
    }
    return s;
}
int main(){
    int n, b, t, d, e, x;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("zero2.in", "r");
    fout=fopen("zero2.out", "w");
    for(t=10; t; t--){
        fscanf(fin, "%d%d", &n, &b);
        d=2;
        ans=-1;
        while(d*d<=b){
            if(b%d==0){
                e=1;
                b/=d;
                while(b%d==0){
                    e++;
                    b/=d;
                }
                x=apar(n, d)/e;
                if((ans==-1)||(ans>x)) ans=x;
            }
            d++;
        }
        if(b!=1){
            x=apar(n, b);
            if((ans==-1)||(ans>x)) ans=x;
        }
        fprintf(fout, "%lld\n", ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}