#include <stdio.h>

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

int 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;
}

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

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

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

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

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

    return 0;
}