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