#include <stdio.h>

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

ll N, B;

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

    for (n = p; n <= N; n++) 
        for (t = n/p; t; t/=p) ret += t;
    return ret;
}

/*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, n, bst, bst_p, bst_e, ret;

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

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

        ret = 0x3f3f3f3f;
        ret = ret*ret;
        bst = bst_p = bst_e = 0;
        for (p = 2; p*p <= B; p++)
        {
            if (B%p) continue;
            for (e = 0, n = 1; !(B%p); B /= p) e++, n *= p;
            if (bst < n)
                bst = n, bst_p = p, bst_e = e;
        }
        if (B > 1 && bst < B)
            bst = B, bst_p = B, bst_e = 1;

        ret = solve(N, bst_p)/bst_e;

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

    return 0;
}