#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int t;
int main(){
    scanf("%d",&t);
    while(t--){
        int a,b;
        scanf("%d%d",&a,&b);
        int ans=0;
        while(a!=0&&b!=0){
            if(b>=a)b-=a;
            else a-=b;
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}