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

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

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


}

}