Vasya is studying number theory. He has denoted a function f(a, b) such that:

  * f(a, 0) = 0; 
  * f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b. 



Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

Input

The first line contains two integer numbers x and y (1 ≤ x, y ≤ 1012).

Output

Print f(x, y).

Examples

Input

3 5


Output

3


Input

6 3


Output

1
#include <bits/stdc++.h>
using namespace std;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
long long where, who;
void tenta(long long d, long long k) {
  long long x = k % d;
  long long w = k - x;
  if ((w > where) or (w == where and d > who)) {
    where = w;
    who = d;
  }
}
long long go(long long n, long long k) {
  if (k == 0) return 0;
  if (k == 1) return 1;
  if (n == 1) return k;
  long long some = 0;
  long long aqui = 0;
  where = -1;
  who = -1;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (i > 1) {
        tenta(i, k);
      }
      tenta(n / i, k);
    }
  }
  if (who != -1) {
    some = 1;
    aqui = k - where;
    k = where;
    k /= who;
    n /= who;
  }
  if (!some) return k;
  return aqui + go(n, k);
}
long long n;
long long k;
long long res;
long long brute() {
  long long b = k;
  long long r = 0;
  while (b > 0) {
    b -= gcd(b, n);
    r++;
  }
  return r;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> k;
  cout << go(n, k) << "\n";
  return 0;
  for (n = 1; n <= 100; n++) {
    for (k = 1; k <= 200; k++) {
      res = go(n, k);
      if (brute() != res) {
        cout << "ops " << n << " " << k << " " << brute() << " " << res << "\n";
        return 0;
      }
    }
  }
}
