#include<stdio.h>

const int maxn = 10000;

long long i;
long long n;
long long k;
long long b;
long long el[maxn],put[maxn];
long long nr;
long long sum;
long long mini;

long long min(long long a, long long b)
{
        if (a<b) return a;
        return b;
}

long long calc(long long n, long long p)
{
        k = n/p - 1;
        return (long long)k*(k+1)/2*p+(k+1)*(n-(k+1)*p+1) ;

}

int main()
{
        freopen("zero2.in","r",stdin);
        freopen("zero2.out","w",stdout);
        int i1;
        for(i1 = 1; i1 <= 10; ++i1)
        {
                scanf("%lld %lld",&n,&b);
                nr = 0;
                
                for(i = 2; i*i <= b; ++i)
                        if (b % i == 0)
                        {
                                nr++;
                                el[nr] = i;
                                put[nr] = 0;
                                while(b % i == 0)
                                {
                                        ++put[nr];
                                        b /= i;
                                }
                                
                        }
               if (b != 1)
               {
                        ++nr;
                        el[nr] = b;
                        put[nr] = 1;
               }
               mini =(long long) 1000000000*1000000000;
               for(i = 1; i <= nr; ++i)
               {
                        long long p = 1;
                        sum = 0;
                        while(p <= n)
                        {
                                p *= el[i];
                                sum += calc(n,p);
                        }
                        mini = min(sum/put[i],mini);
               }
               printf("%lld\n",mini);
        }
        return 0;

}