# include <fstream>
# define INF 1000000000
# define DIM 34000
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
long long f[DIM],d[DIM],n,B,a,k,i,j;
long long minim,b;
long long putere(long long &val,long long x){
    long long nr=0;
    while(val%x==0){
        nr++;
        val/=x;
    }
    return nr;
}
long long factori(long long n,long long x){
    if(x>n)
        return 0;
    long long nr=1LL*((n/x-1)*(n/x)/2)*x+(n/x)*(n%x+1);
    return nr+factori(n,x*d[j]);
}
int main () {
    for(i=2;i<=DIM-50;i++)
        if(f[i]==0){
            d[++k]=i;
            for(j=2*i;j<=DIM-50;j+=i)
                f[j]=1;
        }
    for(i=1;i<=10;i++){
        fin>>n>>B;
        minim=1LL*INF*INF;
        for(j=1;j<=k;j++){
            a=putere(B,d[j]);
            b=factori(n,d[j]);
            if(a==0)
                continue;
            minim=min(minim,b/a);
        }
        if(B!=1){
            a=1;
            d[k+1]=B;
            j=k+1;
            b=factori(n,B);
            minim=min(minim,b);
        }
        fout<<minim<<"\n";
    }
    return 0;
}