I. Евклид и его шаги

Наибольший общий делитель считается рекурсивно: $\gcd(a, 0) = a$, а иначе $\gcd(a, b) = \gcd(b, a \bmod b)$.

Выведите НОД двух чисел и число шагов — сколько раз пришлось применить второе правило.

Например, для 21 и 13: $\gcd(21,13) \to \gcd(13,8) \to \gcd(8,5) \to \gcd(5,3) \to \gcd(3,2) \to \gcd(2,1) \to \gcd(1,0)$ — шесть шагов, ответ 1.

Одна строка содержит числа $a$ и $b$ ($0 \le a, b \le 10^{18}$).

Два числа через пробел: наибольший общий делитель и количество шагов.