#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define min(a,b) (a<b?a:b)

long long n,b,p,pow,i,j,sol,t,k,s,pp,ss;

int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);

    for (t=0;t<10;++t)
    {
        scanf("%ld%ld",&n,&b);
        sol=-1;
        for (p=2;p*p<=b;p++)
        {
            pow=0;
            if (b%p==0)
            {
                while (b%p==0)
                    b/=p,++pow;
                s=0,pp=p;
                do
                {
                    k=n/pp-1;
                    ss=k*(k+1)*pp/2+(k+1)*(n-(k+1)*pp+1);
                    s+=ss,pp*=p;
                }
                while (ss>0);
                if (sol==-1)
                    sol=s/pow;
                else
                    sol=min(sol,s/pow);
            }
        }
        if (b>1)
        {
            p=b,pow=0;
            if (b%p==0)
            {
                while (b%p==0)
                    b/=p,++pow;
                s=0,pp=p;
                do
                {
                    k=n/pp-1;
                    ss=k*(k+1)*pp/2+(k+1)*(n-(k+1)*pp+1);
                    s+=ss,pp*=p;
                }
                while (ss>0);
                if (sol==-1)
                    sol=s/pow;
                else
                    sol=min(sol,s/pow);
            }
        }
        printf("%ld\n",sol);
    }

    return 0;
}