#include <stdio.h>
#include <string.h>

const int baza = 10000;
#define OUTPUT_FORMAT "%04d"

class huge
{
private:
	int a[16];
public:
	huge() { memset(a, 0, sizeof(a)); a[0] = 1; }
	huge (long long n)
	{
		memset(a, 0, sizeof(a));
		if (n == 0)
			a[0] = 1;
		else
		{
			for (; n; n /= baza)
				a[++a[0]] = (int)(n % baza);
		}
	}

	huge operator =(huge A) { memcpy(a, A.a, sizeof(a)); return *this; }

	huge operator +(huge B)
	{
		huge C; int i, t = 0;
		for (i = 1; i <= a[0] || i <= B.a[0] || t; i++, t /= baza)
		      C.a[i] = (t += a[i] + B.a[i]) % baza;
		C.a[0] = i - 1;
		return C;
	}
	
	huge operator +=(huge B)
	{
		int i, t = 0;
		for (i = 1; i <= a[0] || i <= B.a[0] || t; i++, t /= baza)
		      a[i] = (t += a[i] + B.a[i]) % baza;
		a[0] = i - 1;
		return *this;
	}

	huge operator *(huge B)   
	{   
		int i, j, t; huge C;
		for (i = 1; i <= a[0]; i++)   
		{   
				for (t = 0, j = 1; j <= B.a[0] || t; j++, t /= baza)   
					C.a[i + j - 1] = (t += C.a[i + j - 1] + a[i] * B.a[j]) % baza;
				if (i + j - 2 > C.a[0]) C.a[0] = i + j - 2;
		}   
		return C;
	}

	huge operator /=(int B)
	{
		int i, t = 0;
		for (i = a[0]; i > 0; i--, t %= B)
			a[i] = (t = t * baza + a[i]) / B;
		for (; a[0] > 1 && !a[a[0]]; a[0]--);
		return (*this);
	}

	int operator <(huge B)
	{
		int i;
		if (a[0] < B.a[0])
			return 1;
		if (a[0] > B.a[0])
			return 0;

		for (i = a[0]; i; i--)
			if (a[i] != B.a[i])
				if (a[i] < B.a[i])
					return 1;
				else
					return 0;
		return 0;
	}

	void print()
	{
		int i;
		printf("%d", a[a[0]]);
		for (i = a[0] - 1; i; i--)
			printf(OUTPUT_FORMAT, a[i]);
		printf("\n");
	}
};


int N, B;
int put[16], fac[16];
huge NR;

void get( int N, int p )
{
	huge tmp;
	NR = 0;
	for (long long i = p; i <= (long long)N; i *= p)
	{
		//0    i     2i    3i
		//00000111111222222333333...
		long long nrexpr = N / i - 1;
		if (nrexpr % 2 == 0)
		{
			tmp = nrexpr / 2;
			tmp = tmp * (nrexpr + 1);
		}
		else
		{
			tmp = nrexpr;
			tmp = tmp * ((nrexpr + 1) / 2);
		}

		tmp = tmp * i;
		tmp += (N % i + 1) * (N / i);

		NR += tmp;
	}
}

int main()
{
	freopen("zero2.in", "rt", stdin);
	freopen("zero2.out", "wt", stdout);

	int T;
	for (T = 1; T <= 10; T++)
	{
		scanf("%d %d", &N, &B);
		fac[0] = 0;
		if ((B & 1) == 0)
		{
			fac[++fac[0]] = 2;
			put[ fac[0] ] = 0;
			for (; (B & 1) == 0; B >>= 1)
				put[ fac[0] ]++;
		}

		for (int i = 3; i * i <= B; i += 2)
			if (B % i == 0)
			{
				fac[++fac[0]] = i;
				put[ fac[0] ] = 0;
				for (; B % i == 0; B /= i)
					put[ fac[0] ]++;
			}

		if (B > 1)
			fac[++fac[0]] = B,
			put[ fac[0] ] = 1;

		huge MIN;
		get(N, fac[1]);
		NR /= put[1];
		MIN = NR;

		for (int i = 2; i <= fac[0]; i++)
		{
			get(N, fac[i]);
			NR /= put[i];

			if (NR < MIN)
				MIN = NR;
		}
		MIN.print();
	}
	return 0;
}