T = int(input())
results = []

for _ in range(T):
    A, B = map(int, input().split())
    operations = 0

    while A != 0 and B != 0:
        if A > B:
            operations += A // B
            A %= B
        else:
            operations += B // A
            B %= A

    results.append(str(operations))

print("\n".join(results))