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

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

int main(){
    int 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=100000000000000001;
        cb=b;
        div=2;
        bi=div;
        put=1;
        int putereaa=0;
        if(cb%div==0){
            p=solve(div);
            while(cb%div==0){
                cb/=div;putereaa++;
            }
            p=p/putereaa;
            if(p<minim)
                minim=p;
        }
        div++;
        while(cb!=1){
            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=p;

            }
            div+=2;
        }
        printf("%lld\n",minim);
    }
    return 0;
}