#include <cstdio>
#include <climits>
#include <algorithm>

#define ll long long

using namespace std;

ll T , n , b , d , ans , Exp;

ll solve(ll n , ll p)
{
    ll ans = 0;
    for (ll i = p; i <= n; i *= p)
    {
        ll k = n / i - 1;
        ans += i * k * (k + 1) / 2;
        ans += (k + 1) * (n - i * (k + 1) + 1);
    }

    return ans;
}

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

    for (int T = 10; T ; --T)
    {
        scanf("%lld %lld", &n, &b);

        ans = LONG_MAX;

        for (d = 2; d * d <= b; ++d)
            if (b % d == 0)
            {
                for (Exp = 0; b % d == 0; Exp++)
                    b /= d;

                ans = min(ans , solve(n , d) / Exp);
            }

        if (b > 1) ans = min(ans , solve(n , b));

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

    return 0;
}