#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 lgput(LL n, LL k) {
    LL a = n, sol = 1;
    while (k>0) {
        if(k&1) sol*=a;
        a*=a;
        k>>=1;
    }
    return sol;
}

LL nr_zr(LL a, LL b) {
    LL sol = 0;
    //cout << a << ' ' << b << '\n';
    while (a > 0) {
        sol += (((a+1)*a)/2)/b;
        //sol += a/b;
        a /= b;
    }
    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);
        //cout << x << ' ';
    }
    //cout << '\n';
    return minim;
}

void afis() {
    int i;
    cout << lg << '\n';
    for (i = 1; i <= lg; i++)
        cout << fct[i] << ' ' << exp[i] << '\n';
    cout << '\n';
}

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