#include<stdio.h>
int main(){
long long int a,b,i;
int n,j;

        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("%lld", i);


}
return 0;
}