#include<bits/stdc++.h>
using namespace std;
using ll=long long;
///ofstream file("output0.txt");
void solve()
{
    ll a,b; cin>>a>>b;
    ll ans=0;
    while(a>0 && b>0)
    {
        ll mx=max(a,b);
        ll mn=min(a,b);
        ll x = mx/mn;
        ans += x;
        a = mn;
        b = mx-(x*mn);
    }
    cout<<ans<<endl;
    //file<<ans<<endl;
}
int main(){
    int t; cin>>t; while(t--) solve();
//file.close();
}