#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y;
        if(x<y)swap(x,y);
        int sum=0;
        while(y){
            sum+=x/y;
            int n=x%y;
            x=y;
            y=n;
        }
        cout<<sum<<endl;
    }
    return 0;
}