#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define ll long long
#define inf 2000000000

#define Dmax 100

int N, B;
int fact[Dmax], put[Dmax], nrf;
ll put2[Dmax];
ll rez;

int main()
{
	freopen("zero2.in", "r", stdin);
	freopen("zero2.out", "w", stdout);
	
	int stp, i, j;
	int aux, cnt;
	int nr, a1, r;
	ll best;
	
	for (stp = 0; stp < 10; ++stp)
	{	
		scanf("%d %d", &N, &B);
		
		aux = B;
		nrf = 0;
		for (i = 2; i*i <= aux; ++i) if (aux % i == 0)
		{
			for (cnt = 0; aux % i == 0; aux /= i, ++cnt)
			fact[++nrf] = i;
			put[nrf] = cnt;
		}
		if (aux > 1) fact[++nrf] = aux, put[nrf] = 1;
		
		memset(put2, 0, sizeof(put2));
		best = inf;
		for (i = 1; i <= nrf; ++i)
		{
			for (j = fact[i]; j <= N; j *= fact[i])
			{
				r = j;
				a1 = (N-j+1)%j;
				nr = (N-j+1)/r + 1;
				
				put2[i] += (ll)a1*nr + (ll)r*nr*(nr-1)/2;
			}
			best = min(best, put2[i]/put[i]);
		}
		
		printf("%lld\n", best);
	}
	
	return 0;
}