//#include <cmath>
#include <cstdio>
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#define LL  long long
//#define INF 1000000007
//------------------------------------------------------------
//struct P{};
//------------------------------------------------------------
//void Max(int &num1,int num2) { if (num1<num2) num1=num2; }
//void Min(int &num1,int num2) { if (num1>num2) num1=num2; }
//int  Min(int  num1,int num2) { return num1<num2? num1 :num2;}
//------------------------------------------------------------
int  tcase;
int  icase;

int  n,m;
int  i,j,k;

int  ans;
//------------------------------------------------------------
void work(int a,int b)
{
    if (b==0) return;
    ans+=(a/b);
    work(b,a%b);
}
//------------------------------------------------------------
int  main( )
{
    for (scanf("%d",&tcase); ++icase<=tcase; printf("%d\n",ans))
    {
        //--0 init
        scanf("%d%d",&n,&m);
        ans=0;
        
        work(n,m);
    }
}