#include <cstdio>
#include <algorithm>

using namespace std;
int p, q, F;
int gpf(int x)
{
    int d = 2, io;
    do
    {
        if (x % d == 0)
            io = d;
        while((x % d) == 0)
            x /= d;
        if (d * d >= x)
            return max(io, x);
        d ++;
    }
    while(x != 1);
    return io;
}
int nf(int x)
{
    int s = 0;
    while(x)
    {
        x /= F;
        s += x;
    }
    return s;
}
int bs(int fq)
{
    int i = 0, pas = 1 << 15;
    while(pas)
    {
        if(nf(i + pas) < fq)
            i += pas;
        pas /= 2;
    }
    return i;
}
int main()
{
    freopen("gfact.in ", "r", stdin);
    freopen("gfact.out", "w", stdout);
    scanf("%d %d", &p, &q);
    F = gpf(p);
    int k = bs(q);
    if(nf(k + 1) != q) printf("-1\n");
    printf("%d\n", k + 1);
    return 0;
}