#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
int x,y,ans,T;

void gcd(int a,int b)
{
    if (!b) return;
    ans+=a/b;
    gcd(b,a%b);
}


int main()
{
    cin>>T;
    while (T--)
    {
        scanf("%d%d",&x,&y);
        ans=0;
        gcd(x,y);
        cout<<ans<<endl;
    }
}