#include <fstream>

using namespace std;

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

typedef long long i64;

const i64 inf= (i64)1<<62;
const int nmax= 100;

i64 p[nmax+1], e[nmax+1];

i64 f( i64 n, i64 p ) {
    i64 k= n/p;
    return k*(k-1)/2*p+k*(n-k*p+1);
}

int main(  ) {
    for ( int t= 10; t>0; --t ) {
        i64 n, b;
        fin>>n>>b;

        int k= 0;
        for ( int i= 2; i*i<=b; ++i ) {
            if ( b%i==0 ) {
                ++k;
                p[k]= i;
                e[k]= 0;
                while ( b%i==0 ) {
                    b/= i;
                    ++e[k];
                }
            }
        }
        if ( b>1 ) {
            ++k;
            p[k]= b;
            e[k]= 1;
        }
    
        i64 min= inf;
        for ( int i= 1; i<=k; ++i ) {
            int s= 0;
            for ( int j= p[i]; j<=n; j*= p[i] ) {
                s+= f(n, j);
            }
            s/= e[i];
            if ( s<min ) {
                min= s;
            }
        }

        fout<<min<<"\n";
    }

    return 0;
}