def min_operations_to_zero(A, B):
    count = 0
    while A > 0 and B > 0:
        if A > B:
            A -= B
        else:
            B -= A
        count += 1
    return count

def main():
    T = int(input())
    for _ in range(T):
        A, B = map(int, input().split())
        result = min_operations_to_zero(A, B)
        print(result)

if __name__ == "__main__":
    main()