#include<fstream>
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
unsigned long long n,i,j,b,sol,minim,p,nr;
int main(){
    for(i=1;i<=10;i++){
        fin>>n>>b;
        minim=1000000000000000005;
        for(j=2;j<=b/j;j++){
            if(b%j==0){
                nr=0;
                while(b%j==0){
                    nr++;
                    b/=j;
                }
                p=j;
                sol=0;
                while(p<=n){
                    sol+=(n/p-1)*(n/p)/2*p+(n/p)*(n%p+1);
                    p*=j;
                }
                if(sol/nr<minim){
                    minim=sol/nr;
                }
            }
        }
        if(b!=1){
            p=b;
            sol=0;
            while(p<=n){
                sol+=(n/p-1)*(n/p)/2*p+(n%p+1)*(n/p);
                p*=b;
            }
            if(sol<minim){
                minim=sol;
            }
        }
        fout<<minim<<"\n";
    }
    return 0;
}