#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>

#define LL long long

using namespace std;

int a,b,c,d,m,n,u,v,w;

int main()
{
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        LL ans=0LL;
        while(n!=1&&m!=1){
            if(n>m)swap(n,m);
            if(n==0||m==0)break;
            ans+=m/n;
            m=m%n;
        }
        if(n==0||m==0){
            cout<<ans<<endl;
            continue;
        }
        if(m==1) ans+=n;
        else ans+=m;
        cout<<ans<<endl;
    }
    return 0;
}