#include <stdio.h>

#define FIN "zero2.in"
#define FOUT "zero2.out"
#define ll long long
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mult 0x3f3f3f3f

ll N, B;

ll solve(ll N, ll p)
{
    ll t, k, ret = 0;

    for (t = p; t <= N; t *= p)
    {
        k = N/t;
        ret += (ll)t*k*(k-1)/2;
        ret += (ll)(N-k*t+1)*k;
    }
    return ret;
}

int main(void)
{
    ll t, p, e, ret;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    for (t = 0; t < 10; t++)
    {
        scanf("%lld %lld", &N, &B);

        ret = mult;
        ret *= ret;
        for (p = 2; p*p <= B; p++)
        {
            if (B%p) continue;
            for (e = 0; !( B%p ); B /= p) e++;
            ret = min(ret, solve(N, p)/e);
        }
        if (B > 1) ret = min(ret, solve(N, B)); 

        printf("%lld\n", ret);
    }

    return 0;
}