#include<iostream>
#include<cstdio>
#define N 100005
using namespace std;
int main()
{
  int t;
  cin>>t;
  while (t--)
  {
       int n,m,cnt=0;
       scanf("%d%d",&n,&m);
       if (n>m) {
                int t=n;
                n=m;
                m=t;
                } 
       while (n)
       {
       cnt+=m/n;
        m=m%n;
        if (n>m) {
                int t=n;
                n=m;
                m=t;
                }   
          
       }
  printf("%d\n",cnt);
  }    
}