#include<stdio.h>
void exchangge(int *a,int *b){
    int temp;
    if(*a>*b){
        temp=*a;
        *a=*b;
        *b=temp;
    }
}
int main(){
    int n,m;
    int sum;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        exchangge(&n,&m);
        sum=0;
        while(n!=0){
            //printf("%d %d\n",n,m);
            sum+=m/n;
            m%=n;
            exchangge(&n,&m);
        }
        printf("%d\n",sum);
    }
    return 0;
}