Заданы два числа. До тех пор, пока оба они больше нуля, с ними производят одну и ту же операцию: из большего числа вычитают меньшее. Если числа равны, то из одного вычитают другое. Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).
Вам задано некоторое количество пар (ai, bi). Сколько операций будет выполнено для каждой из них?
Выходные данные
Выведите искомое количество операций для каждой пары на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 17
7 987654321
|
8
141093479
|