# include <stdio.h>
# include <stdlib.h>

# define int long long

int nrZero( int nr, int baza ) {
    int k;

    k = 0;
    while ( nr ) {
        nr /= baza;
        k += nr;
    }

    return k;
}

int src( int nr, int baza ) {
    int pos, pas;
    pos = 0;
    for ( pas = 40; pas >= 0; pas -- )
        if ( nrZero( pos + ( 1LL << pas ), baza ) < nr )
            pos += ( 1LL << pas );

    return pos + 1;
}

int srcA( int nr, int pow ) {
    int d, p, max, c;

    max = 0;
    for ( d = 2; d * d <= nr; d ++ ) {
        if ( nr % d == 0 ) {
            p = 0;
            while ( nr % d == 0 ) {
                nr /= d;
                p ++;
            }
            if ( p > 0 ) {
                c = src( pow * p, d );
                if ( c > max )
                    max = c;
            }
        }
    }

    if ( nr > 1 )
        max = src( pow, nr );

    return max;
}

int main() {
    FILE *fin = fopen( "gfact.in", "r" ), *fout = fopen( "gfact.out", "w" );

    int p, q;

    fscanf( fin, "%lld%lld", &p, &q );

    fprintf( fout, "%lld", srcA( p, q ) );

    fclose( fin );
    fclose( fout );

    return 0;
}