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

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

    if (a==0) break;
}
else{
    b=abs(a-b);

     if (b==0) break;
}

}
printf("%d", i);


}

}