#include <bits/stdc++.h>
using namespace std;
const int maxn = (1e6) + 7;
const int inf = (1e9) + 7;
const long long LLinf = (1e18) + 7;
const long double eps = 1e-9;
long long nw(long long a, long long b) {
  if (a == 0LL || b == 0LL) return max(a, b);
  return nw(max(a, b) % min(a, b), min(a, b));
}
long long a;
vector<long long> P;
bool czy(long long A, long long nwd, long long p) {
  while (nwd % p == 0) {
    nwd /= p;
    A /= p;
  }
  if (A % p == 0) return 1;
  return 0;
}
long long wyn(long long b) {
  if (a == b) return 1LL;
  if (b == 0LL) return 0LL;
  long long nwd = nw(a, b);
  long long ile = LLinf;
  long long y = b / nwd;
  for (auto s : P) {
    if (czy(a, nwd, s)) ile = min(ile, y % s);
  }
  if (ile == LLinf) return y;
  return ile + wyn(b - nwd * ile);
}
int main() {
  long long B;
  cin >> a >> B;
  long long c = a;
  for (long long i = 2LL; i * i <= a; i++) {
    if (c % i == 0) P.push_back(i);
    while (c % i == 0) c /= i;
  }
  if (c > 1LL) P.push_back(c);
  cout << wyn(B);
  return 0;
}
