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

long long cmmd( long long nr ) {
    long long d;

    for ( d = 2; d * d <= nr; d ++ )
        if ( nr % d == 0 )
            return nr / d;
    return nr;
}

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

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

    return k;
}

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

    if ( nrZero( pos + 1, baza ) == nr )
        return pos + 1;
    else
        return -1;
}

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

    long long p, q;

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

    fprintf( fout, "%lld", src( q, cmmd( p ) ) );

    fclose( fin );
    fclose( fout );

    return 0;
}