/*
Bismillahir Rahmanir Rahim
(In the name of Allah)

@Author Muhammad Nadim
*/

#include<bits/stdc++.h>
using namespace std;

#define     ll              long long
#define     ld              long double
#define     nl              '\n'
#define     pi              acos(-1.0)
#define     sp(n)           fixed<<setprecision(n)
#define     MNTDH_18        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define     yes             cout<<"YES"<<"\n"
#define     no              cout<<"NO"<<"\n"
#define     all(v)          v.begin(), v.end()
#define     CheckBit(x, k)  (x & (1LL << k))
#define     SetBit(x, k)    (x |= (1LL << k))
#define     ClearBit(x, k)  (x &= ~(1LL << k))
#define     LSB(mask)       __builtin_ctzll(mask)
#define     MSB(mask)       63-__builtin_clzll(mask) 

template <typename T, typename U> T ceil(T x, U y) {return (x > 0 ? (x + y - 1) / y : x / y);}
template <typename T, typename U> T floor(T x, U y) {return (x > 0 ? x / y : (x - y + 1) / y);}

//typedef  __int128 lll;
typedef struct rafi
{
    ll type;
    ll idx1;
    ll idx2;
}R;

typedef struct sajeeb
{
    ll val1;
    ll val2;
}S;

typedef struct ohi
{
    ll l;
    ll r;
    ll u;
    ll d;
    int val;
}O;

const int N=2e5+7, M=1073741824, N1=60;
ll p[N1];

void pow2()
{
    p[0]=1;
    for(int i=1; i<N1; i++) p[i]=2*p[i-1];
}

void sF()
{
    ll a, b, cnt=0, mod;
    cin>>a>>b;

    ll mx=max(a, b);
    ll mn=min(a, b);

    while(mn)
    {
        cnt+=(mx/mn);

        ll mx0=max(mx, mn);
        ll mn0=min(mx, mn);

        mx0%=mn0;

        mx=max(mx0, mn0);
        mn=min(mx0, mn0);

        //cout<<cnt<<" "<<mx<<" "<<mn<<nl;
    }
    cout<<cnt<<nl;
}

int main()
{
    MNTDH_18
    //pow2();

    int tc=1, cs=1;
    cin>>tc;
    
    while(tc--)
    {
        //cout<<"Case "<<cs++<<": ";
        sF();
    }

    return 0;
}