#include <fstream>
#define a1 (N%D+1)
#define r (D)
#define n (N/D)
using namespace std;

long long N,B;

long long Solve() {

    int i,P;
    long long Sum,D;

    for(D=2,P=0;B%D==0;P++)
        B/=D;

    for(i=3;i*i<=B;i+=2)
        if(B%i==0) {
            D=i;
            P=0;
            while(B%i==0)
                B/=i,P++;
            }

    if(B>1)
        D=B,P=1;

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

    return (Sum/P);

}
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;

}