#include <stdio.h>
#include <vector>
#define dbg if(debug)
using namespace std;

bool debug = true;
vector<int> prime;
bool *pr;
const int t = 10;

void ciur ( int lim ) {
	pr = (bool*) malloc(lim*sizeof(bool));
	pr[0] = false;
	for (int i = 1; i<lim; ++i) {
		pr[i] = true;
	}
	for (int i = 2; i<=lim; ++i) {
		if (pr[i]) {
			prime.push_back(i);
			for (int j = 2; i*j<=lim; ++j) {
				pr[i*j] = false;
			}
		}
	}
	free(pr);
}

int main() {
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	
	int n[t], b[t];
	int maxb = 0;
	for (int i = 0; i<t; ++i) {
		scanf("%d %d",&n[i],&b[i]);
		if (b[i] > maxb) maxb = b[i];
	}
	ciur(maxb);
	for (int i = 0; i<t; ++i) {
		dbg fprintf(stderr,"  Testul %d: %d %d\n",i,n[i],b[i]);
		int s = 2000000000;
		for (vector<int>::iterator j = prime.begin(); j != prime.end() && *j <= b[i]; ++j) {
			if (b[i] % *j == 0) {
				dbg fprintf(stderr,"baza %d se imparte la %d\n",b[i],*j);
				int exp = 0;
				for (int aux = b[i]; aux % *j == 0; aux /= *j, ++exp);
				dbg fprintf(stderr,"exponentul este %d\n",exp);
				int s1 = 0;
				for (int d = *j; d<=n[i]; d *= *j) {
					dbg fprintf(stderr,"%d -> ",d);
					for (int k = n[i]%d+1; k<=n[i]; k += d) {
						dbg fprintf(stderr,"%d ",k);
						s1 += k;
					}
					dbg fprintf(stderr,"\n");
				}
				dbg fprintf(stderr,"%d apare de %d ori in %d\n",*j,s1,n[i]);
				if (s1 / exp < s) s = s1 / exp;
			}
		}
		printf("%d\r\n",(s==2000000000)?0:s);
	}
	return 0;
}