#include <cstdio>
#include <iostream>

const int maxp = 31630;
const int nrp = 3406;

FILE *in = fopen("zero2.in","r"), *out = fopen("zero2.out","w");

int k;
int pr[nrp];
int exp[maxp];

int isprimeB;

int z;
int facts[nrp];

int N, B;

void erast()
{
    char x[maxp];

    for ( int i = 2; i < maxp; i += 2 )
        x[i] = 'x';

    pr[k++] = 2;

    for ( int i = 3; i < maxp; i += 2 )
        if ( x[i] != 'x' )
        {
            pr[k++] = i;

            for ( int j = i*i; j < maxp; j += i )
                x[j] = 'x';
        }
}

void fact()
{
    for ( int i = 0; pr[i]*pr[i] <= B; ++i )
        while ( B % pr[i] == 0 )
            B /= pr[i], ++exp[ pr[i] ], facts[z++] = pr[i];

    if ( B > 1 )
        isprimeB = 1;
}

long long S(long long pr)
{
    long long k = (N / pr) - 1;

    return k * (k+1)/2*pr + (k+1)*(N-(k+1)*pr+1);
}

long long nr(int pr)
{
    long long sol = 0;
    int p = pr;
    long long pp = pr;

    long long t;
    while ( (t = S(pp)) )
        sol += t, pp *= p;


    return sol;
}

int main()
{
    erast();

    int w, h;
    for ( int j = 0; j < 10; ++j )
    {
        fscanf(in, "%d %d", &w, &h);
        N = w, B = h;

        fact();

        long long answ = 0;
        if ( exp[ facts[0] ] )
            answ = nr( facts[0] ) / exp[ facts[0] ];
        else
            answ = nr ( B );

        for ( int i = 1; i < z; ++i )
        {
            long long t = nr( facts[i] ) / exp[ facts[i] ];
            if ( t < answ )
                answ = t;
        }

        if ( isprimeB )
        {
            long long t = nr( B );
            if ( t < answ )
                answ = t;
            isprimeB = 0;
        }

        fprintf(out, "%lld\n", answ);
        z = 0;
        memset(exp, 0, maxp);
    }



	return 0;
}