You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (*a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>). How many operations will be performed for each of them?
The first line contains the number of pairs *n* (1  ≤  *n*  ≤  1000). Then follow *n* lines, each line contains a pair of positive integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1  ≤  *a*<sub class="lower-index">*i*</sub>,  *b*<sub class="lower-index">*i*</sub>  ≤  10<sup class="upper-index">9</sup>).
"""
Заданы два числа. До тех пор, пока оба они больше нуля, с ними производят одну и ту же операцию: из большего числа вычитают меньшее.
Если числа равны, то из одного вычитают другое. Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).

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

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

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


def count_v(n1, n2):
    k = 0
    while n1 > 0 and n2 > 0:
        if n1 >= n2:
            n1 -= n2
        else:
            n2 -= n1
        k += 1
    return k


n = int(input())
for i in range(n):
    n1, n2 = map(int, input().split())
    print(count_v(n1, n2))
