#include<cstdio>
#include<algorithm>
using namespace std;
long long n,b,k,ans;
long long pr[100];
long long e[100];
long long S(long long n,long long p)
{
    long long k=n/p-1;
    return k*(k+1)/2*p+(k+1)*(n-(k+1)*p+1);
}
int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);
    for(int p=1;p<=10;p++)
    {
        scanf("%lld%lld",&n,&b);k=0;
        for(int i=2;i*i<=b;++i)
            if(b%i==0)
            {
                pr[++k]=i; e[k]=0;
                while(b%i==0)
                    b/=i,e[k]++;
            }
        if(b>1)
            pr[++k]=b,e[k]=1;
        ans=1LL<<60;
        for(int i=1;i<=k;++i)
        {
            long long r=0,j=pr[i];
            while(j<=n)
                r+=S(n,j),j*=pr[i];
            r/=e[i];
            ans=min(ans,r);
        }
        printf("%lld\n",ans);
    }
    return 0;
}