#include <cstdio>
using namespace std;
bool ciur[110005];
int prime[100005], div[15], k;
const long long MAX = 2305843009213693952;
void form_prime(long long n){
    int i;
    long long j;
    k = 1; prime[1] = 2;
    for (i = 3; i <= n; i += 2)
        if (!ciur[i]){
            prime[++k] = i;
            for (j = 1LL * i * i; j <= n; j += 2 * i)
                ciur[j] = 1;
        }
}
int divizori(long long n){
  int d, nrdiv = 0;
  for (d = 1; prime[d] * prime[d] <= n && d <= k; d ++){
      if (n % prime[d] == 0){
          div[++nrdiv] = prime[d];
          while (n % prime[d] == 0)
              n /= prime[d];
      }
  }
  if (n > 1)
      div[++nrdiv] = n;
  return nrdiv;
}
long long submultimi(int n, long long a){
  int i, j, card, ok;
  long long ns, prod, ans = a;
  ns = (1 << n) - 1;
  for (i = 1; i <= ns; i ++){
      card = 0;
      prod = 1;
      for (j = 0; j < n; j ++)
          if ((1 << j) & i){
              prod = 1LL * prod * div[j + 1];
              card ++;
          }
      if (card % 2 == 1)
          ok = -1;
      else
          ok = 1;
      ans = ans + 1LL * ok * a / prod;
  }
  return ans;
}
long long bs(long long st, long long dr, long long val, int nrdiv){
  long long med, last = -1, ans;
  while (st <= dr){
    med = (st + dr) >> 1;
    ans = submultimi(nrdiv, med);
    if (ans >= val){
        last = med;
        dr = med - 1;
    }
    else
        st = med + 1;
  }
  return last;
}
int main(){
  freopen("frac.in", "r", stdin);
  freopen("frac.out", "w", stdout);
  int t, i, nrdiv;
  long long a, b;
  form_prime(110000);
  scanf("%lld%lld", &a, &b);
  nrdiv = divizori(a);
  printf("%lld\n", bs(1, MAX, b, nrdiv));
  return 0;
}