n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    count = 0
    while (a != 0 and b != 0):
        s1 = max(a,b)
        if s1 == a:
            a = a - b
            count = count + 1
        elif s1 == b:
            b = b - a
            count = count + 1
    print(count)