#include <cstdio>
#include <algorithm>

using namespace std;

#define ll long long

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, add = 1;
    ll ans = 0, nr = prime;
    while ( nr <= ( ll ) n ) {
        ll limit = min( nr * prime - 1, ( ll ) n );
        ans += ( limit - nr + 1 ) * ( ll ) multiply;

        ++add;
        multiply += add;
        nr += ( ll ) 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 );
}