#include <fstream>
#define oo (1LL<<61)
#define a1 (N%i+1)
#define r (i)
#define n (N/i)
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
 
long long N,B;
 
long long Result(long long D) {
 
    long long Sum,i;
 
    for(i=D,Sum=0;i<=N;i*=D)
        Sum+=n*(2*a1+r*(n-1))/2;
 
    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;
 
}