#include <fstream>
#include <iostream>
#define LL long long

using namespace std;

ifstream f("zero2.in");
ofstream g("zero2.out");

bool prim[40005];
int np[10005], N;
int fct[10005], exp[10005], lg;
LL a, b;

void ciur(int n) {
    int i, j;
    np[N = 1] = 2;
    for (i = 3; i <= n; i += 2)
        if (prim[i] == 0) {
            np[++N] = i;
            for (j = 3*i; j <= n; j += 2*i)
                prim[j] = 1;
        }

}

void desc(LL b) {
    int i;
    LL b1 = b;
    lg = 0;
    for (i = 1; b1 > 1; i++) {
        if (b1 % np[i] == 0) {
            fct[++lg] = np[i];
            exp[lg] = 0;
            while (b1 % np[i] == 0)
                exp[lg]++, b1 /= np[i];
        }
        if (np[i] * np[i] > b1 && b1 > 1) {
            fct[++lg] = b1;
            exp[lg] = 1;
            b1 = 1;
        }
    }
}

LL gauss_div_like_iter(LL a, LL b) { // [1/b] + [2/b] + [3/b] + ... + [a/b] in complexitate O(1)
    LL y = a/b-1;
    LL sol = b*y*(y+1)/2;
    sol += ((a%b)+1)*(y+1);
    return sol;
}

LL nr_zr(LL a, LL b) {
    LL sol = 0, x, y;
    while (a > 0) {
        sol += gauss_div_like_iter(a, b);
        //cout << gauss_div_like_iter(a, b) << ' ';
        a /= b;
    }
    //cout << '\n';
    return sol;
}

LL calculam() {
    int i;
    LL minim = 3e16, x;
    for (i = 1; i <= lg; i++) {
        x = nr_zr(a, fct[i]);
        minim = min(minim, x);
    }
    return minim;
}

int main() {
    ciur(39990);
    //cout << gauss_div_like_iter(8, 3);
    for (int zz = 1; zz <= 10; zz++) {
        f >> a >> b;
        desc(b);
        g << calculam() << '\n';
    }
    return 0;
}