A. Рациональное сопротивление
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Безумный ученый Майк в свободное время строит машину времени. Для окончания проекта ему понадобился резистор с определенным значением сопротивления.

Однако у Майка в запасе есть только большое количество одинаковых резисторов с единичным сопротивлением R0 = 1. Элементы с другим сопротивлением можно собирать из данных резисторов. В данной задаче элементами будем считать:

  1. один резистор;
  2. элемент и один резистор, подключенные последовательно;
  3. элемент и один резистор, подключенные параллельно.

При последовательном подключении сопротивление нового элемента равно R = Re + R0. При параллельном подключении сопротивление нового элемента равно . В данном случае Re равняется сопротивлению подключаемого элемента.

Майку нужно собрать элемент с сопротивлением, равным дроби . Определите наименьшее количество резисторов, с помощью которых можно собрать такой элемент.

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

В единственной строке входных данных через пробел записаны два целых числа a и b (1 ≤ a, b ≤ 1018). Гарантируется, что дробь несократима. Гарантируется, что решение всегда существует.

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

Выведите единственное число — ответ на задачу.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
1 1
Выходные данные
1
Входные данные
3 2
Выходные данные
3
Входные данные
199 200
Выходные данные
200
Примечание

В первом примере хватает одного резистора.

Во втором примере можно соединить два резистора параллельно, а полученный элемент соединить последовательно с третьим резистором. Таким образом получаем элемент с сопротивлением . С помощью двух резисторов такой элемент построить невозможно.