def min_operations(a, b):
    
    count = 0

    while a != 0 and b != 0:
        
        a, b = abs(a - b), min(a, b)
        count += 1

   
    return count

if __name__ == "__main__":
    T = int(input()) 

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