#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=111111;
int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int a,b,cnt=0;
        cin>>a>>b;
        while(1)
        {
            if(a<b)swap(a,b);
            a-=b;
            if(min(a,b)>=1)cnt++;
            else{
                break;
            }
        }
        cout<<cnt+1<<endl;
    }
}