E. Васина функция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася изучает теорию чисел. Он определил функцию f(a, b) следующим образом:

  • f(a, 0) = 0;
  • f(a, b) = 1 + f(a, b - gcd(a, b)), где gcd(a, b) это наибольший общий делитель a и b.

У Васи есть два числа x и y, и он хочет вычислить f(x, y). Он хотел сделать это сам, но его способ может занять слишком много времени. Так что он просит вас написать программу, с помощью которой можно посчитать эту функцию быстро.

Входные данные

Первая и единственная строка содержит два целых числа x и y (1 ≤ x, y ≤ 1012).

Выходные данные

Выведите f(x, y).

Примеры
Входные данные
3 5
Выходные данные
3
Входные данные
6 3
Выходные данные
1