#include <iostream>
#include <fstream>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long  N,B;
long long mini=LLONG_MAX;
long long suma(long long a)
{
    long long k=N/a;
    return k*(k-1)/2*a+(N-k*a+1)*k;
}
void functie1(long long p, int e)
{
    long long S=0,P=p;
    while(P<=N)
    {
        S+=suma(P);
        if(P>N/p) break;
        P*=p;
    }
    if(S>=e)
    if(mini>S/e) mini=S/e;
}
void descfp(int n)
{
    int e=0;
    if(n%2==0)
    {
        while(n%2==0)
        {
            n/=2;
            e++;
        }
        functie1(2,e);
        e=0;
    }
    for(long long d=3;d*d<=n&&n>1;d+=2)
    {
        if(n%d==0)
    {
        while(n%d==0)
        {
            n/=d;
            e++;
        }
        functie1(d,e);
        e=0;
    }
    }
    if(n>1)
    functie1(n,1);

}
int main()
{
    for(int i=1;i<=10;i++)
    {
        f>>N>>B;
        descfp(B);
        if(mini==LLONG_MAX)
            g<<0<<endl;
            else
        g<<mini<<endl;
        mini=LLONG_MAX;
    }
    return 0;
}