#include <fstream>
#include <cmath>
using namespace std;

int main()
{
    ifstream in("zero2.in");
    ofstream out("zero2.out");
    long long factors[60][2], n, b, mn;
    short n_factors;
    for(short i=0; i<10; ++i)
    {
        n_factors=0;
        in>>n>>b;
        for(short j=2; j<=sqrt(b); ++j)
        {
            if(!(b%j))
            {
                factors[n_factors][0]=j;
                factors[n_factors][1]=1;
                ++n_factors;
                b/=j;
            }
            while(!(b%j))
            {
                ++factors[n_factors-1][1];
                b/=j;
            }
        }
        if(b>1)
        {
            factors[n_factors][0]=b;
            factors[n_factors][1]=1;
            ++n_factors;
        }
        mn=123456789101112;
        for(short j=0; j<n_factors; ++j)
        {
            long long aux=factors[j][0];
            long long ctr=0;
            while(n/aux)
            {
                ctr+=(n/aux)*(n/aux-1)/2*aux+(n/aux)*(n%aux+1);
                aux*=factors[j][0];
            }
            if(ctr/factors[j][1]<mn)
            {
                mn=ctr/factors[j][1];
            }
        }
        out<<mn<<'\n';
    }
    in.close(); out.close();
    return 0;
}