Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.

However, all Mike has is lots of identical resistors with unit resistance *R*_{0} = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:

- one resistor;
- an element and one resistor plugged in sequence;
- an element and one resistor plugged in parallel.

With the consecutive connection the resistance of the new element equals *R* = *R*_{e} + *R*_{0}. With the parallel connection the resistance of the new element equals . In this case *R*_{e} equals the resistance of the element being connected.

Mike needs to assemble an element with a resistance equal to the fraction . Determine the smallest possible number of resistors he needs to make such an element.

The single input line contains two space-separated integers *a* and *b* (1 ≤ *a*, *b* ≤ 10^{18}). It is guaranteed that the fraction is irreducible. It is guaranteed that a solution always exists.

Print a single number — the answer to the problem.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.

提交代码