A. Вычитания
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы два числа. До тех пор, пока оба они больше нуля, с ними производят одну и ту же операцию: из большего числа вычитают меньшее. Если числа равны, то из одного вычитают другое. Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).

Вам задано некоторое количество пар (ai, bi). Сколько операций будет выполнено для каждой из них?

Входные данные

В первой строке задано количество пар n (1  ≤  n  ≤  1000). Далее идут n строк, каждая содержит пару целых положительных чисел ai, bi (1  ≤  ai,  bi  ≤  109).

Выходные данные

Выведите искомое количество операций для каждой пары на отдельной строке.

Примеры
Входные данные
2
4 17
7 987654321
Выходные данные
8
141093479