#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

#define L 45

int div[300], exp[300];
int nrdiv, q;

uint64_t divd(uint64_t n, int d) {
    uint64_t nr = 0;
    while (n >= d)
        nr += n /= (uint64_t)d;
    return nr;
}

bool okek(uint64_t n) {
    int i = 0;
    while (i < nrdiv && divd(n, div[i]) >= (uint64_t)exp[i] * q)
        i++;
    return i >= nrdiv;
}

int main()
{
    FILE *fin, *fout;
    int p, pc, d, e, i;
    uint64_t pas, r;

    fin = fopen("gfact.in", "r");
    fscanf(fin, "%d%d", &p, &q);
    fclose(fin);
    pc = p;

    d = 2;
    nrdiv = 0;
    while (d * d <= p) {
        if (p % d == 0) {
            e = 0;
            while (p % d == 0) {
                e++;
                p /= d;
            }
            div[nrdiv] = d;
            exp[nrdiv] = e;
            nrdiv++;
        }
        d++;
    }
    if (p > 1) {
        div[nrdiv] = p;
        exp[nrdiv] = 1;
        nrdiv++;
    }

    pas = 1LL << L;
    r = 0LL;
    while (pas != 0) {
        if (!okek(r + pas)) {
            r += pas;
        }
        pas >>= 1LL;
    }

    fout = fopen("gfact.out", "w");
    if (pc > 1)
        fprintf(fout, "%lld", r + 1);
    else
        fprintf(fout, "0");
    fclose(fout);
    return 0;
}