#include <iostream>
#include <fstream>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
const long long INF=0x3f3f3f3f;
long long n,b,cate,put[20],exp[20],rez[20];

void descomp(int x) {
    cate=0;
    for(int d=2; d*d<=x; d++) {
        int k=0;
        while(x%d==0) {
            x/=d;
            k++;
        }
        if(k>0) {
            put[++cate]=d;
            exp[cate]=k;
        }
    }
    if(x>1) {
        put[++cate]=x;
        exp[cate]=1;
    }
}

void rezo(int n) {
    for(int i=1; i<=cate; i++) {
        long long p=put[i];
        rez[i]=0;
        while(p<=n) {
            int k=n/p;
            rez[i]+=p*k*(k-1)/2;
            rez[i]+=(n-k*p+1)*k;
            p*=put[i];
        }
    }
}

int main() {
    for(int i=1; i<=10; i++) {
        f>>n>>b;
        descomp(b);
        long long minim=INF;
        rezo(n);
        for(int j=1; j<=cate; j++) {
            minim=min(minim,rez[j]/exp[j]);
        }
        g<<minim<<"\n";
    }
    f.close();
    g.close();
    return 0;
}