#include <iostream>
#include <cstdio>
using namespace std;

int T,n,m,w,ans;

void dg(int x,int y)
{
    ans+=y/x;
    if(y%x==0)return;
    int z=x;
    x=y-y/x*x;
    y=z;
    dg(x,y);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        
        ans=0;dg(n,m);
        printf("%d\n",ans);
    }
    return 0;
}