/**
*	author: shafi
*	created: 06.03.2024 17.12.19
**/
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define ull unsigned long long int

int main(){
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int tc;
    cin>>tc;
    while(tc--){
        ll a,b;
        cin>>a>>b;
        if(b>a) swap(a,b);
        ll cnt = 0;
        while(true){
            a = a-b;
            cnt++;
            if(b>a)swap(a,b);
            if(a<=0 || b <= 0) break;
        }
        cout<<cnt<<endl;
    }
    return 0;
}