#include<cstdio>
#include<algorithm>
#define Minim(x, y) (x <= y ? x : y)
#define DIM 100
using namespace std;
long long N, B, k, sol;
long long v[DIM], ex[DIM];

long long AUX(long long, long long);

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

        for (int p = 1; p <= 10; p++)
        {
            scanf("%lld%lld", &N, &B);
            k = 0;

            for (int i = 2; i * i <= B; i++)
                if (B % i == 0)
                {
                    v[++k] = i; ex[k]=0;
                    while (B % i == 0)
                        B /= i, ex[k]++;
                }
            if (B > 1)
                v[++k] = B, ex[k]=1;

            sol = 1LL << 60;
            for (int i = 1; i <= k; i++)
            {
                long long r = 0, j = v[i];
                while( j <= N)
                {
                    r += AUX(N, j);
                    j *= v[i];
                }
                r /= ex[i];
                sol = Minim(sol, r);
            }
            printf("%lld\n", sol);
        }
    }

long long AUX(long long n, long long p)
{
    long long k = n / p - 1;
    return k * (k + 1) / 2 * p + (k + 1) * (n - (k + 1) * p + 1);
}