#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tc;
    cin >> tc;
    while(tc--)
    {
        long long a,b;
        cin >> a >> b;
        long long op=0;
        while(a!=0 && b!=0)
        {
            long long mx = max(a,b);
            long long mn = min(a,b);
            op += mx/mn;
            mx %= mn;
            a = mx;
            b = mn;
        }
        cout << op << endl;
    }
    return 0;
}