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;
long long int mcd(long long int a, long long int b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return mcd(a % b, b);
}
long long int mcm(long long int a, long long int b) {
  return a / mcd(a, b) * b;
}
long long int absolut(long long int x) {
  if (x < 0) return -x;
  return x;
}
void chino(long long int a, long long int b, long long int &ca,
           long long int &cb, long long int d) {
  if (absolut(a) < absolut(b)) {
    chino(b, a, cb, ca, d);
    return;
  }
  if (b == 0) {
    ca = d / a;
    cb = 0;
    return;
  }
  chino(a % b, b, ca, cb, d);
  cb -= ca * (a / b);
}
long long int pasos(long long int mc, long long int b, long long int d) {
  if (b < d) return -1;
  long long int bmodd = b % d;
  if (bmodd % mcd(mc, b) != 0) return -1;
  long long int cmc, cb;
  chino(b, mc, cb, cmc, bmodd);
  long long int salto = mcm(b, mc) / mc;
  cmc %= salto;
  if (cmc < 0) cmc += salto;
  return cmc;
}
long long int sol = 0;
vector<long long int> divisores;
void avanza(long long int a, long long int &b) {
  long long int mc = mcd(a, b);
  if (mc == a) {
    sol += b / mc;
    b = 0;
    return;
  }
  long long int pas = b / mc;
  for (int i = int(divisores.size()) - 1; i >= 0 and divisores[i] > mc; i--) {
    long long int d = divisores[i];
    long long int nextpas = pasos(mc, b, d);
    if (nextpas != -1 and nextpas < pas) pas = nextpas;
  }
  b -= pas * mc;
  sol += pas;
}
int main() {
  long long int a, b;
  cin >> a >> b;
  for (long long int d = 1; d * d <= a; d++) {
    if (a % d == 0) {
      divisores.push_back(d);
      long long int o = a / d;
      if (o != d) divisores.push_back(o);
    }
  }
  sort(divisores.begin(), divisores.end());
  while (b != 0) avanza(a, b);
  cout << sol << endl;
}
