#include <iostream>
using namespace std;

typedef long long ll;

int musa(ll A, ll B) 
{
    int operations = 0;
    while (A != 0 && B != 0) 
    {
        if (A > B) 
        {
            operations += A / B;
            A %= B;
        }
        else 
        {
            operations += B / A;
            B %= A;
        }
    }
    return operations;
}

int main() 
{
    int T;
    cin >> T;

    while (T--) 
    {
        ll A, B;
        cin >> A >> B;
        cout << musa(A, B) << endl;
    }

    return 0;
}