#include <fstream>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long suma_legendre(long long N, long long p)
{
    long long v = 0, a = p;
    while(a <= N)
    {
        long long k = N / a;
        long long t1 = (k % 2 == 0) ? (a * (k / 2) * (k - 1)) : (a * k * ((k - 1) / 2));
        long long t2 = (N - k * a + 1) * k;
        v += t1 + t2;
        a *= p;
    }
    return v;
}

int main()
{
    long long N, B;
    for(int j = 1; j <= 10; j++)
    {
        f >> N >> B;
        long long mini = 0;
        int ok = 0;
        for(long long i = 2; i * i <= B; i++)
            if(B % i == 0)
            {
                int putere = 0;
                while(B % i == 0)
                {
                    putere++;
                    B /= i;
                }
                long long v = suma_legendre(N, i);
                long long nr = v / putere;
                if(ok == 0)
                {
                    ok = 1;
                    mini = nr;
                }
                if(nr < mini)
                    mini = nr;
            }
        if(B > 1)
        {
            long long v = suma_legendre(N, B);
            if(ok == 0)
            {
                ok = 1;
                mini = v;
            }
            if(v < mini)
                mini = v;
        }
        g << mini << '\n';
    }
    return 0;
}