#include <fstream>

using namespace std;
const long long INF = 4611686018427387904;

int Fp[15], Ex[15], Nf;
long long Expf[15];

ifstream in("zero2.in");
ofstream out("zero2.out");

void desc(int x)
{
    Nf = 0;
    for(int d = 2; d * d <= x; d += (d == 2) ? 1 : 2)
        if(x % d == 0)
        {
            Fp[++Nf] = d;
            Ex[Nf] = 0;
            while(x % d == 0)
                Ex[Nf]++, x /= d;
        }
    if(x > 1)
        {
            Fp[++Nf] = x;
            Ex[Nf] = 1;
        }
}

long long calcul(int N)
{
    for(int i = 1; i <= Nf; i++)
        Expf[i] = 0;
    long long nrz = INF;
    for(int i = 1; i <= Nf; i++)
    {
        long long pow = Fp[i];
        while(N >= pow)
        {
            long long exp = N / pow;
            Expf[i] += pow * exp * (exp - 1) / 2;
            Expf[i] += exp * (N - exp * pow + 1);
            pow *= Fp[i];
        }
        nrz = min(nrz, Expf[i] / Ex[i]);
    }
    return nrz;
}

int main()
{
    int N, B;
    for(int i = 1; i <= 10; i++)
    {
        in >> N >> B;
        desc(B);
        out << calcul(N) << '\n';
    }
    in.close();
    out.close();
    return 0;
}