#include <fstream>
#define oo (1LL<<61)
#define a1 (N%D+1)
#define r (D)
#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 P) {

    long long Sum;

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

    return (Sum/P);

}
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,1));

    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;

}