#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

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

long long frecventa_numar(int n,int b){
    long long aux = 1;
    long long nr = 0;
    while(aux*b <= n){
        aux *= b;
        nr += 1LL*(n/aux - 1)*(n/aux)/2*aux;
        nr += 1LL*(n%b+1)*(n/aux);
    }
    return nr;
}

long long rez(int n,int b){
    int d = 2,exp = 0;
    long long minim = LLONG_MAX;

    while(d*d <= b){
        exp = 0;
        while(b % d == 0){
            b /= d;
            exp++;
        }
        if(exp)
            minim = min(minim,frecventa_numar(n,d)/exp);
        d++;
    }
    if(b > 1)
        minim = min(minim,frecventa_numar(n,b));

    return minim;
}


int main()
{
    int n,b;
    for(int i = 1; i <= 10; i++){
        in>>n>>b;
        out<<rez(n,b)<<"\n";
    }
    return 0;
}