#include <cstdio>

int power( int n, int b ) {
    int count = 0;
    if ( b == 2 || b == 4 || b == 8 ) {
        while ( n ) {
            count += n >> 1;
            n >>= 1;
        }
        
        return count;
    }

    if ( b == 3 || b == 6 || b == 9 ) {
        while ( n ) {
            count += n / 3;
            n /= 3;
        }

        return count;
    }

    if ( b == 5 || b == 10 ) {
        while ( n ) {
            count += n / 5;
            n /= 5;
        }

        return count;
    }

    while ( n ) {
        count += n / 7;
        n /= 7;
    }

    return count;
}

long long solve( int n, int b ) {
    long long ans = 0;
    for ( int i = 2; i <= n; ++i ) 
        ans += ( long long ) power( i, b );
    if ( b == 4 || b == 9 )
        ans /= 2;
    else if ( b == 8 )
        ans /= 3;
    return ans;
}

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