def min_operations_to_zero(A, B):
    count = 0
    while A > 0 and B > 0:
        count += A // B
        A, B = B, A % B
    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()