#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
int main()
{
  int n,t,m;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d",&n,&m);
    int ans=min(n,m);
    int cnt=max(n,m);
    int pos=cnt/ans;int res=cnt%ans;
    int sum=0;sum+=pos;
    while(res!=0)
    {
      cnt=ans;ans=res;res=cnt%ans;
      sum+=cnt/ans;
    }
    printf("%d\n",sum);
  }
}