#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;
}