#include<stdio.h>
#include<stdlib.h>
int k, b;
struct ches{
	int a, b, c;
};
ches desc[10000000];
int wop(int ww, int vv){
	int i;
	long long t=1;
	for (i=1;i<=vv;i++)
		t*=ww;
	return t;
}
void dcp(){
	int i, j;
	i=2;
	while (b>1){
		if (b%i==0){
			j=0;
			do{
				j++;
				b=b/i;
			}
			while (b%i==0);
			desc[k].a=wop(i,j);
			desc[k].b=i;
			desc[k].c=j;
			k++;
		}
		i++;
	}
}
int comp(const void*x, const void*y){
	ches xx=*(ches*)x, yy=*(ches*)y;
	if (xx.a<yy.a) return 1;
	if (xx.a>yy.a) return -1;
	return 0;
}
void gol(){
	int i;
	for (i=0;i<k;i++){
		desc[i].a=0;
		desc[i].b=0;
	}
}
int main(){
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	int i, n, q, j;
	long long s;
	for (i=0;i<10;i++){
		scanf("%d%d",&n,&b);
		dcp();
		qsort(desc,k,sizeof(desc[0]),comp);
		s=0;
		for (j=desc[0].b;j<=n;j*=desc[0].b){
			q=n/j;
			if (q!=0)
				s+=q*(n+1)-j*q*(q+1)/2;
		}
		printf("%lld\n",s/desc[0].c);
		gol();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}