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

using namespace std;

#define ll long long

#define Dmax 1000

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

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

		for (i = 1; i <= nrf; ++i)
		{
			for (j = fact[i]; j <= N; j *= fact[i])
			{
				r = j;
				a1 = (N-j+1)%r;
				nr = (N-j+1)/r + 1;
				
				put2[i] += a1*nr + r*nr*(nr-1)/2;
			}
			if (best == 0 || put2[i]/put[i] < best)
			best = put2[i]/put[i];
		}
		
		printf("%lld\n", best);
	}
	
	return 0;
}