#include <bits/stdc++.h>
using namespace std;
#define IOS  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int M = 3e5 + 5, MOD = 998244353;
int32_t main()
{
    int x;
    cin>>x;
    for(int i = 0;i < x;i++)
    {
        int a,b;
        cin>>a>>b;
        int total = 0;
        for(int j = 0;;j++)
        {
            if(a > b)
            {
                a = a - b;
                total++;
            }
            else if(a < b)
            {
                b = b - a;
                total++;
            }
            else
            {
                a = a- b;
                total++;
            }
            if(a == 0 || b == 0)
            {
                break;
            }
        }
        cout<<total;
    }
    return 0;
}