#include <iostream>
#include <fstream>
using namespace std;
ifstream si("zero2.in");
ofstream so("zero2.out");
long long p[105], d[105];
int main() {
    for(int t=10; t>0; t--) {
        long long n, b;
        si>>n>>b;
        int k=0;
        for(int i=2; 1LL*i*i<=b; i++) {
            if(b%i==0) {
                k++;
                d[k]=i;
                p[k]=0;
                while(b%i==0) {
                    b/=i;
                    p[k]++;
                }
            }
        }
        if(b>1) {
            k++;
            d[k]=b;
            p[k]=1;
        }
        long long minn=(1LL<<62);
        for(int i=1; i<=k; i++) {
            long long s=0;
            for(long long j=d[i]; j<=n; j*=d[i]) {
                long long nr=n/j;
                nr=nr*(nr-1)/2*j+nr*(n-nr*j+1);
                s+=nr;
            }
            s/=p[i];
            if(s<minn) {
                minn=s;
            }
        }
        so<<minn<<'\n';
    }
    return 0;
}