#include <cstdio>
#include <algorithm>

using namespace std;

#define ll long long
#define INF 0x3f3f3f3f

void desc( int n, int &prime, int &exp ) {
    for ( int p = 2; p * p <= n; ++p )
        if ( n % p == 0 ) {
            prime = p;
            exp = 0;
            while ( n % p == 0 ) {
                ++exp;
                n /= p;
            }
        }
    if ( n > 1 ) {
        prime = n;
        exp = 1;
    }
}

ll solve( int n, int b ) {
    int prime, exp;
    desc( b, prime, exp );
    
    int multiply = 1, nr = prime;
    ll ans = 0;
    while ( nr <= n ) {
        int limit = min( nr + prime - 1, n );
        ans += ( ll ) ( limit - nr + 1 ) * multiply;
        
        multiply++;
        nr += prime;
    }

    return ( ll ) ans / exp;
}

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 );
}