#include <iostream>
using namespace std;
int main(){
    int t,m,n;
    cin>>t;
    for (int ii=0;ii<t;ii++){
        cin>>n>>m;
        if (n>m) swap(n,m);
        int ans=0;
        while (n!=0){
            ans+=m/n;
            int tmp=m%n;
            m=n;
            n=tmp;
        }
    cout<<ans<<endl;
    }
    return 0;
}