#include <fstream>
#define oo (1LL<<61)
#define n (N/D)
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

long long N,B;

long long Result(long long D) {

    long long Sum;

    for(Sum=0;D<=N;D*=D)
        Sum+=D*n*(n-1)/2+(N-D*n+1)*n;

    return Sum;

}
long long Solve() {

    int i;
    long long Ans,D,P;

    Ans=oo;

    for(i=2;i*i<=B;i++)
        if(B%i==0) {

            D=i;
            P=0;
            while(B%i==0)
                B/=i,P++;

            Ans=min(Ans,Result(D)/P);

            }

    if(B>1)
        Ans=min(Ans,Result(B));

    return Ans;

}
int main() {

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

    for(int T=10;T;T--) {
        in>>N>>B;
        out<<Solve()<<'\n';
        }

    in.close();
    out.close();

    return 0;

}