#include<fstream>

using namespace std;

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

const unsigned long long inf = (unsigned long long)(1 << 63) - 1;
int n;
unsigned long long ans;

void exp( int d, int e ) {
    unsigned long long k = 0;
    for( int p = d; p <= n; p *= d ) {
        for( int i = p; i <= n; i += p ) {
            k += (n - i + 1);
        }
    }
    k /= e;
    if ( k < ans ) {
        ans = k;
    }
    return ;
}
int main() {
    int x, b, 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;
}