#include <stdio.h>
#include <vector>
using namespace std;

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) {
		int s = 2000000000;
		for (vector<int>::iterator j = prime.begin(); j != prime.end() && *j <= b[i]; ++j) {
			if (b[i] % *j == 0) {
				int exp = 0;
				for (int aux = b[i]; aux % *j == 0; aux /= *j, ++exp);
				int s1 = 0;
				for (int d = *j; d<=n[i]; d *= *j) {
					for (int k = n[i]%d+1; k<=n[i]; k += d) {
						s1 += k;
					}
				}
				if (s1 / exp < s) s = s1 / exp;
			}
		}
		printf("%d\n",(s==2000000000)?0:s);
	}
	return 0;
}