#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
    int cas; scanf("%d",&cas);
    while (cas--){
        int x,y,ans=0; scanf("%d%d",&x,&y);
        while (x && y){
            if (x<y) swap(x,y);
            ans+=x/y; x%=y;
        }
        printf("%d\n",ans);
    }
    return 0;
}