Безумный ученый Майк в свободное время строит машину времени. Для окончания проекта ему понадобился резистор с определенным значением сопротивления.
Однако у Майка в запасе есть только большое количество одинаковых резисторов с единичным сопротивлением R0 = 1. Элементы с другим сопротивлением можно собирать из данных резисторов. В данной задаче элементами будем считать:
- один резистор;
- элемент и один резистор, подключенные последовательно;
- элемент и один резистор, подключенные параллельно.
При последовательном подключении сопротивление нового элемента равно R = Re + R0. При параллельном подключении сопротивление нового элемента равно 
. В данном случае Re равняется сопротивлению подключаемого элемента.
Майку нужно собрать элемент с сопротивлением, равным дроби 
. Определите наименьшее количество резисторов, с помощью которых можно собрать такой элемент.
Выходные данные
Выведите единственное число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере хватает одного резистора.
Во втором примере можно соединить два резистора параллельно, а полученный элемент соединить последовательно с третьим резистором. Таким образом получаем элемент с сопротивлением 
. С помощью двух резисторов такой элемент построить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
1
|
|
2
|
3 2
|
3
|
|
3
|
199 200
|
200
|