#include<cstdio>
using namespace std;
long long n,b,put,bi;

long long solve(long long bb){
    long long p2=1,rid=0;
    if(bb>n)
        return 0;
    long long rez=1;
    long long d=n/bb;
    rez=rez*(n*d +d -bb*((d*(d+1)/2)));
    return rez+solve(bb*bi);
}

int main(){
    long long cb,div;
    long long p,minim;
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    for(int i=1;i<=10;i++){
        scanf("%d%d",&n,&b);
        minim=-1;
        cb=b;
        long long putereaa=0;
        div=2;
        while(cb!=1&&div*div<=cb){
            put=1;
            bi=div;
            putereaa=0;
            if(cb%div==0){
                p=solve(div);
                while(cb%div==0){
                    cb/=div;putereaa++;
                }
                p=p/putereaa;
                if(p<minim||minim==-1)
                    minim=p;

            }
            div++;
        }
        if(cb!=1){
            bi=cb;
            put=1;
            p=solve(cb);
            if(p<minim||minim==-1)
                minim=p;
        }

        printf("%lld\n",minim);
    }
    return 0;
}