#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
int t,x,y,cnt,a,b;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&y);
        cnt=0;
        while(1)
        {
            if(x==y) break;
            cnt++;
            a=min(x,y);
            b=max(x,y);
            x=min(a,b-a);
            y=max(a,b-a);
        }
        printf("%d\n",cnt+1);
    }
}