def min_operations_to_zero(A, B):
    # Initialize the count of operations
    count = 0
    
    # Continue the operation until either A or B becomes zero
    while A > 0 and B > 0:
        # Update the maximum of A and B
        max_val = max(A, B)
        min_val = min(A, B)
        
        # Update the value of max(A, B)
        A = abs(max_val - min_val)
        B = min_val
        
        # Increment the count of operations
        count += 1
    
    # Add the remaining operations if one of them is not zero
    count += max(A, B)
    
    return count

# Number of test cases
T = int(input())

for _ in range(T):
    # Input for each test case
    A, B = map(int, input().split())
    
    # Find and print the minimum number of operations
    result = min_operations_to_zero(A, B)
    print(result)