#include<stdio.h>
int main(){
int a,b,j,n,i;
        scanf("%d", &n);
for(j=1;j<=n;j++){

    scanf("%d %d", &a,&b);
for(i=1;;i++){
if(a>b){
    a=abs(a-b);
}
else{
    b=abs(a-b);

}
if (a==0||b==0) break;
}
printf("%d", i);


}

}