#include <fstream>
#include <math.h>
using namespace std;

ifstream fi ("zero2.in");
ofstream fo ("zero2.out");

int N, B, NF;
unsigned long long Nr, Nrd;
struct { int d, c; } F[15];

unsigned long long min (unsigned long long a, unsigned long long b)
{
	if (a < b) return a;
	return b;
}

void descompune (int N)
{
	double r = sqrt (N);
	NF = -1;
	
	for (int d = 2; d <= r; ++d)
		if ( !(N % d) )
		{
			F[++NF].d = d;
			F[NF].c = 0;
			while ( !(N % d) )
			{
				++F[NF].c;
				N /= d;
			}
		}
	if ( N != 1)
	{	
		F[++NF].d = N;
		F[NF].c = 1;
	}		
}

unsigned long long fact_primi2 (int D)
{
	unsigned long long NrN, NRed, NRed2, NrRed;
	NrN = N / D;
	NRed = NrN * D;
	NRed2 = NRed - D + 2;
	NrRed = (NRed2 * NrN) / 2;
	return NrRed + (N - NRed) * NrN; 
}

unsigned long long fact_primi (int D)
{
	unsigned long long P = D, Nr = 0;
	while (P <= N)
	{
		Nr += fact_primi2 (P);
		P *= D;
	}
	return Nr;	
}

int main ()
{
	for (int t = 0, d; t < 10; ++t)
	{
		fi >> N >> B;
		descompune (B);
		
		for (d = 0; d <= NF; ++d)
		{
			Nrd = fact_primi (F[d].d) / F[d].c;
			if (d == 0)
				Nr = Nrd;
			else
				Nr = min (Nr, Nrd);
		}
		fo << Nr << '\n';
	}
	return 0;
}