keverek = []

def lnko(a,b):
    while a != b:
        if a > b:
            a = a-b
        else:
            b = b-a
    return b

for i in range(1,501):
    for j in range(1,501):
        if lnko(i,j) == 1:
            keverek.append([i,j])

keverek.sort(key=lambda x: x[0]+x[1])

T = int(input())
for _ in range(T):
    A,B = map(int,input().split())

    db = 0

    for i,j in keverek:
        if i <= A and j <= B:
            db += 1
            A -= i
            B -= j
        if A == 0 or B == 0 or (A < i and B < j):
            break

    print(db)