#include <cstdio>
#include <algorithm>
using namespace std;
int t,m,n;
int main()
{int i,j,x,y;
 scanf("%d",&t);
 while(t--)
 {
 int ans=0;
 scanf("%d%d",&m,&n);
 if(m>n)swap(m,n);
 while(m)
 {ans+=n/m;
  x=n;
  n=m;
  m=x%m;
   }
  printf("%d\n",ans);
}
 return 0;
}