#include <fstream>

using namespace std;

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

int n, i, j, b;
int np[30000], nf;
bool p[35000];

void ciur() {
    int i, j;
    for (i = 2; i*i <= 1000000000; i++)
        if (!p[i]) {
            np[++nf] = i;
            for (j = i*2; 1LL*j*j <= 1000000000; j+=i)
                p[j] = 1;
    }

}

int do_it() {
    int i, j;
    int b1 = b;
    int exp, emin = 1e+6, bmin;
    int nd = 0;
    int sn = 0;

    for (i = 1; np[i] <= b1 && i <= nf; i++) {
        if (b1%np[i] == 0) {
            nd++;
            exp = 0;
            while (b1%np[i] == 0)
                b1 /= np[i], exp++;
            if (emin > exp)
                emin = exp, bmin = np[i];
        }
    }
    //g << nd << ' ';
    if (nd == 0)
        bmin = b;
    while (n)
        sn += n/bmin, n /= bmin;
    return sn;
}

int main() {
    ciur();
    for (i = 1; i <= 10; i++) {
        f >> n >> b;
        g << do_it() << '\n';
    }
    return 0;
}