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

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


}

}