Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Заданы два числа. До тех пор, пока оба они больше нуля, с ними производят одну и ту же операцию: из большего числа вычитают меньшее. Если числа равны, то из одного вычитают другое. Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).
Вам задано некоторое количество пар (ai, bi). Сколько операций будет выполнено для каждой из них?
Входные данные
В первой строке задано количество пар n (1 ≤ n ≤ 1000). Далее идут n строк, каждая содержит пару целых положительных чисел ai, bi (1 ≤ ai, bi ≤ 109).
Выходные данные
Выведите искомое количество операций для каждой пары на отдельной строке.