#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include <iomanip>
#include<stack>
using namespace std;
typedef long long LL;
const LL MAX = (LL)1e5 + 5;
const int eps=1e9+7;

char a[1010];
int  b[1010],len;
int m;
void init()
{

}

void solve()
{

}
int ans;
int main()
{
    ios_base::sync_with_stdio(0);
    int T,n,m;
    cin>>T;
    while(T--)
    {
        ans=0;
        cin>>n>>m;
        while(1)
        {
            if(n<m) swap(n,m);
            ans+=n/m;
            n%=m;
            if(n==0) break;
        }
        cout<<ans<<endl;
    }
    return 0;
}