def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def min_operations_to_zero(A, B):
    gcd_value = gcd(A, B)
    return (A + B) // gcd_value

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()