#include <cstdio>

#define ll long long
#define INF 0x3f3f3f3f

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

ll min( ll a, ll b ) {
    return a < b ? a : b;
}

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 ) {
        ll ans = 0, nr = prime[i];
        while ( nr <= n ) {
            int k = n / ( int ) nr;
            ans += ( ll ) nr * k * ( k - 1 ) / 2;
            ans += ( ll ) ( n - nr * k + 1 ) * k;

            nr *= prime[i];
        }

        res = min( res, ( ll ) 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 );
}