#include<stdio.h>
int max(int x,int y)
{
    if(x>y)return x;
    else return y;
}
int min(int x,int y)
{
    if(x>y)return y;
    else return x;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b;
        int c,d;
        int sum=0;
        scanf("%d%d",&a,&b);
        c=max(a,b);
        d=min(a,b);
        while(c!=d)
        {
        c=c-d;
    //    printf("c %d %d\n",c,d);
        a=c;
        b=d;
        c=max(a,b);
        d=min(a,b);
            sum++;
        }
        printf("%d\n",sum+1);
    }
    return 0;
}