#include<cstdio>
struct aa{long long x,y;};
aa v[15];
void f()
    {long long n,b,i,j,m,x,k,q,nr,sqq,sw,p,min;
    long long s;
    scanf("%lld%lld",&n,&b);
    x=0;
    min=-1;
    for(i=2;i*i<=b;i++)
        if(b%i==0)
            {x++;
            v[x].x=i;
            k=0;
            while(b%i==0)
                {b/=i;
                k++;
                }
            v[x].y=k;
            }
    if(b!=1)
        {x++;
        v[x].x=b;
        v[x].y=1;
        }
    for(i=1;i<=x;i++)
        {s=0;
        q=1;
        nr=0;
        for(j=1;q<=n/v[i].x;j++)
            {q=q*v[i].x;
            nr++;
            }
        q=1;
        for(j=1;j<=nr;j++)
            {q=q*v[i].x;
            k=n-q+1;
            sqq=k%(q*v[i].x);
            sw=k/(q*v[i].x)+1;
            p=(k+sqq)*sw/2;
            s+=p*j;
            }
        if(s/v[i].y<min||min==-1)
            min=s/v[i].y;
        }
    printf("%lld\n",min);
    }
int main ()
{freopen ("zero2.in","r",stdin);
freopen ("zero2.out","w",stdout);
int i;
for(i=1;i<=10;i++)
    f();
return 0;
}