#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
ll t = 10, n, rez, b;

ll putere(ll p) {
    ll put = 0;
    for (ll initial = p; p <= n; p *= initial) {
        ll k = n / p - 1;
        put += (k * (k + 1) / 2) * p + (n - (k + 1) * p + 1) * (k + 1);
    }
    return put;
}

void desc(ll nr) {
    ll div = 2;
    while (nr > 1) {
        ll p = 0;
        while (nr % div == 0)
            nr /= div, ++p;
        if (p > 0)
            rez = min(rez, putere(div) / p);
        ++div;
        if (div * div > nr)
            div = nr;
    }
    return;
}

int main() {
    while (t--) {
        fin >> n >> b;
        rez = 1e12;
        desc(b);
        fout << rez << "\n";
    }
    return 0;
}