#include<iostream>
#include<stdio.h>
using namespace std;
#define N 1010

int main(){
    //freopen("in.txt","r",stdin);
    int T,n,m,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(n<m)
            swap(n,m);
        ans=0;
        while(n%m){
            int t=n/m;
            n%=m;
            ans+=t;
            swap(n,m);
        }
        ans+=n/m;
        cout<<ans<<endl;
    }

    return 0;
}