#include <iostream>
#include <fstream>

using namespace std;

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

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

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

    while(d*d <= b ){
        exp = 0;
        while(b % d == 0){
            b /= d;
            exp++;
        }
        if(exp > 0)
            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;
}