#include<fstream>

using namespace std;

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

typedef unsigned long long i65;

const i65 inf = 9223372036854775807;
i65 n, ans;

void exp( int d, int e ) {
    i65 t, k = 0;
    for( i65 p = d; p <= n; p *= d ) {
        t = n / p;
        k += t * (t - 1) / 2 * p + t * (n - t * p + 1);
    }
    k /= e;
    if ( k < ans ) {
        ans = k;
    }
    return ;
}
int main() {
    i65 x, b;
    int e;
    for( int q = 0; q < 10; ++ q ) {
        fin >> n >> b;
        x = b;
        ans = inf;
        for( int i = 2; i * i <= b && x > 1; ++ i ) {
            e = 0;
            while ( x % i == 0 ) {
                ++ e;
                x /= i;
            }
            if ( e > 0 ) {
                exp( i, e );
            }
        }
        if ( x > 1 ) {
            exp( x, 1 );
        }
        fout << ans << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}