#include<cstdio>
using namespace std;
long long minim(long long a,long long b){
    if(a<b)
        return a;
    return b;
}
long long power(long long n,long long d){
    long long ans=0,p,x;
    for(p=d;p<=n;p*=d){
        x=n/p-1;
        ans=ans+x*(x+1)*p/2+(x+1)*(n-(x+1)*p+1);
    }
    return ans;
}
int main(){
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    int t,p,i;
    long long n,b,sol,d,inf=1;
    for(i=1;i<=62;i++)
        inf*=2;
    for(t=1;t<=10;t++){
        scanf("%lld%lld",&n,&b);
        sol=inf;
        for(d=2;d*d<=b;d++)
            if(b%d==0){
                p=0;
                while(b%d==0){
                    b/=d;
                    p++;
                }
                sol=minim(sol,power(n,d)/p);
            }
        if(b!=1)
            sol=minim(sol,power(n,b));
        printf("%lld\n",sol);
    }
    return 0;
}