#include<fstream>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
ifstream fin("zero2.in");
ofstream fout("zero2.out");
int n,b;
long long minim;
int main()
{
    int d;
    for (int I=0;I<10;++I)
    {
        fin>>n>>b;
        minim=INF;
        for (d=2;d*d<=b;++d)
            if (b%d==0)
            {
                int nr=0;
                long long p,q=0;
                while (b%d==0) ++nr, b/=d;
                for (long long i=d;i<=n;i*=d)
                {
                    p=n/i;
                    q+=p*(p-1)/2*i+(n-p*i+1)*p;
                }
                minim=min(minim,q/nr);
            }
        if (b>1)
        {
            long long p,q=0;
            for (long long i=b;i<=n;i*=b)
            {
                p=n/i;
                q+=p*(p-1)/2*i+(n-p*i+1)*p;
            }
            minim=min(minim,q);
        }
        fout<<minim<<"\n";
    }
    return 0;
}