#include <stdio.h>
#define nmax 31623
#define nrp 3402

bool v[nmax];
long long prim[nrp], cnt;

void ciur();
long long f(long long, long long, long long);

int main()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);

	long long test, n, b, nr, temp, t, sol, i, p;
	ciur();

        
	for(test = 0; test < 10; ++ test)
	{
		scanf("%lld %lld", &n, &b);
		sol = 100000;
		temp = n;
		
		for(i = 1; prim[i] * prim[i] <= temp; ++i)
		{
              p = 0;
              while(temp % prim[i] == 0)
              {
                      temp /= prim[i];
                      ++p;
              }
              if(p)
              {
                   t = f(n, prim[i], p);
                   if(t < sol)
                        sol = t;
              } 
        }
        printf("%lld\n", sol);
	}

	return 0;
}

void ciur()
{
	int i, j;

	for(i = 2; i < nmax; ++i)
	{
		if(!v[i])
		{
			prim[++cnt] = i;
			for(j = 2 * i; j < nmax; j += i)
			{
				v[j] = 1;
			}
		}
	}
}

long long f(long long nr, long long b, long long p)
{
       long long temp = b, s = 0;
       
       while(nr / temp)
       {
                s += (nr / temp) * (nr / temp - 1) / 2 * b;
                s += nr % temp * nr / temp;
                temp *= b;
       }
       return s / p;
}