# include <cstdio>

typedef long long ll ;
const char FIN[] = "zero2.in", FOU[] = "zero2.out" ;
const ll oo = 1LL << 62 ;

int N, B ;

ll min ( ll A, ll B ) {
    return ( A < B ) ? A : B ;
}

ll solve ( int N, int B ) {
    ll sol = 0;

    for ( int i = B; i <= N; i *= B ) {
        int aux = N / i ;
        sol += ( ll ) i * aux * ( aux - 1 ) / 2 + ( ll ) ( N - aux * i + 1 ) * aux ;
    }
    return sol ;
}

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    for ( int T = 10 ; T ; --T ) {
        scanf ( "%d %d", &N, &B ) ;

        ll sol = oo ;
        for ( int i = 2, j; i * i <= B; ++i ) {
            if ( B % i == 0 ) {
                for ( j = 0; B % i == 0; B /= i, ++j ) ;
                sol = min ( sol, solve ( N, i ) / j ) ;
            }
        }
        if ( B > 1 ) {
            sol = min ( sol, solve ( N, B ) ) ;
        }

        printf ( "%lld\n", sol ) ;
    }

    return 0 ;
}