#include <cstdio>
#include <algorithm>

using namespace std;

#define ll long long
#define INF 0x3f3f3f3f

int nrp, prime[20], exp[20];

void desc( int n ) {
    nrp = 0;
    for ( int p = 2; p * p <= n; ++p )
        if ( n % p == 0 ) {
            prime[nrp] = p;
            exp[nrp] = 0;
            while ( n % p == 0 ) {
                ++exp[nrp];
                n /= p;
            }

            ++nrp;
        }
    if ( n > 1 ) {
        prime[nrp] = n;
        exp[nrp] = 1;
        ++nrp;
    }
}

ll solve( int n, int b ) {
    desc( b );
    
    ll res = ( ll ) INF * INF;
    for ( int i = 0; i < nrp; ++i ) {
        int multiply = 1, nr = prime[i];
        ll ans = 0;
        while ( nr <= n ) {
           int limit = min( nr + prime[i] - 1, n );
           ans += ( ll ) ( limit - nr + 1 ) * multiply;

           multiply++;
           nr += prime[i];
        }

        res = min( res, ans / exp[i] );
    }

    return ( ll ) res;
}

int main() {
    FILE *fin, *fout;

    fin = fopen( "zero2.in", "r" );
    fout = fopen( "zero2.out", "w" );

    for ( int i = 0; i < 10; ++i ) {
        int n, b;
        fscanf( fin, "%d%d", &n, &b );

        fprintf( fout, "%lld\n", solve( n, b ) );
    }

    fclose( fin );
    fclose( fout );
}