#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
typedef long long LL;
const int M = 1e9;
int T;
int gcd(int n,int m){
    if(n<m){
      T=n;
      n=m;
      m=T;    
    }
    
    //printf("%d %d\n",n,m);
    if(m==0)
    return 0;
    if(n%m ==0 ) return n/m;
    else return (1 + gcd(n-m,m));
}
int main()
{
    int i,j,k,n,m,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",gcd(n,m));
    }
    return 0;
}