The Euclidean Algorithm

The famous Euclidean algorithm is found in Book VII of the Elements, written around 300 B.C. by the Greek mathematician Euclid. The story goes that King Ptolemy, having looked through the Elements, hopefully asked Euclid whether there was a shorter way to geometry, and Euclid severely answered: "In geometry there is no royal road!" We should probably not blame the King for looking for a short cut, because the Elements runs to thirteen books. The books consist mainly of the mathematical knowledge Euclid amassed, plus some discoveries of his own. Euclid's great achievement is the beautifully systematic presentation of the material as an organic whole. The Elements remained a standard work for over two thousand years. (see Episodes from the Early History of Mathematics, Asger Aaboe)

The modern Euclidean algorithm is usually presented like this.

1. Let $A$ and $B$ be integers with $A > B \geq 0$.
2. If $B = 0$, the gcd is $A$ and the algorithm ends.
3. Otherwise find $q$ and $r$ with $A = qB + r$ and $0 \leq r < B$. Here $0 \leq r < B < A$ and $\gcd(A,B) = \gcd(B,r)$. Replace $A$ by $B$ and $B$ by $r$, then go to Step 2.

The original Euclidean algorithm uses subtraction instead of division. It rests on the observation that a common divisor of the positive integers $A$ and $B$ is also a common divisor of $\min(A,B)$ and $\max(A,B)-\min(A,B)$. So the gcd of two positive integers can be found like this.

1. Let $A$ and $B$ be positive integers.
2. If $A = B$, the gcd is $B$ and the algorithm ends.
3. Otherwise replace $A$ by $\max(A,B)-\min(A,B)$ and $B$ by $\min(A,B)$, then go to Step 2.

Starting from $A = 24$ and $B = 15$, the original algorithm runs as follows.

1. $A = 24-15 = 9$, $B = 15$
2. $A = 15-9 = 6$, $B = 9$
3. $A = 9-6 = 3$, $B = 6$
4. $A = 6-3 = 3$, $B = 3$

That is, before reaching $\gcd(24,15) = 3$, it executes Step 3 four times.

Given two positive integers, count how many times the original Euclidean algorithm executes Step 3.

The input consists of one line containing two positive integers separated by one or more spaces. Neither integer is larger than 32767.

Print one line containing the number of times the original Euclidean algorithm executes Step 3.