#include <fstream>
using namespace std;
ifstream f("zero2.in"); ofstream g("zero2.out");
int main()
{   int n,b,p,exp;
    for(int j=1;j<=10;j++)
    {   f>>n>>b;
        for(int i=2;i*i<=b;i++)
        if (b%i==0)
            for (p=i,exp=0;b%i==0;b/=i) exp++;
        if (b>1) {exp=1;p=b;}
        long long sol,x,k,ret=0;
        for (sol=0,x=p;x<=n;x*=p)
            {
                k=n/x;
                sol=sol+x*(k-1)*k /2 + k * (n%x+1);
                ret+=sol/exp;
                sol%=exp;
            }
        g<<ret<<'\n';
    }
    g.close(); return 0;
}