#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int T;
int a,b;
int main()
{
    cin>>T;
    while(T--)
    {
        int sum=0;
        scanf("%d%d",&a,&b);
        while(a>0&&b>0)
        {
            if(a<b)swap(a,b);
            a-=b;
            sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}