#include <stdio.h>
#include <stdlib.h>

int main(){
    FILE*fi,*fo;
    fi=fopen("zero2.in","r");
    fo=fopen("zero2.out","w");
    for(int i=0;i<10;i++){
        long long n, b;
        fscanf(fi,"%lld%lld", &n, &b);
        long long d=2;
        long long min=1000000000000000000;
        while(d*d<=b){
            if(b%d==0){
                long long exp=0;
                while(b%d==0){
                    exp++;
                    b/=d;
                }
                long long exp2=0, pow=d;
                while(pow<=n){
                    long long k=n/pow;
                    k--;
                    exp2+=k*(k+1)/2*pow+(k+1)*(n-(k+1)*pow+1);
                    pow*=d;
                }
                exp2=exp2/exp;
                if(exp2<min)
                    min=exp2;
            }
            d++;
        }
        if(b>1){
            long long exp2=0, pow=b;
            while(pow<=n){
                long long k=n/pow;
                k--;
                exp2+=k*(k+1)/2*pow+(k+1)*(n-(k+1)*pow+1);
                pow*=b;
            }
            if(exp2<min)
                min=exp2;
        }
        fprintf(fo,"%lld\n", min);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}