/*_______________ H E A D E R S ______________*/
#include <bits/stdc++.h>
#include <stdio.h>
#include <cmath>
/*_______________ M A C R O S ______________*/
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define ll long long int
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define mx_ele(v) *max_element(v.begin(), v.end())
#define mnm_ele(v) *min_element(v.begin(), v.end())
#define endl "\n"
#define vint vector<int>
#define vll vector<long long int>
#define vstring vector<string>
#define pint vector<pair<int, int>>
#define pll vector<pair<ll, ll>>
#define fi first
#define se second
#define mp make_pair
#define Endl endl
#define mod abs
#define PIE 3.141592653589793238462643383279
using namespace std;

/* C O N V E R S I O N    T O     A N Y      N U M B E R    S Y S T E M            ________
      D E C I M A L       T O     A N Y       R A D I X   /   B A S E              ________*/

long long decimal_to_any(long long base, long long num)
{
    if (num == 0)
    {
        return 0;
    }
    long long result = 0;
    long long power = 1;
    while (num > 0)
    {
        long long rem = num % base;
        result += rem * power;
        num /= base;
        power *= 10;
    }
    return result;
}
ll gcd(ll a, ll b)
{
    return (b == 0) ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
    return (a / gcd(a, b)) * b;
}

/*          ->  HOW TO FIND THE NTH TERM OF SEQ <-  ??
Solution:
   ->    formula : a1+(nth-1)*diff;
here,
   >>    a1 is the first element of the seq
   >>    nth is the term we want to find
   >>    diff is the difference of the sq
*/

ll nth_term(ll start_of_seq, ll diff, ll nth)
{
    return start_of_seq + (nth - 1) * diff;
}

//                 G E T   A L L   T H E   P E R M U T A T I O N   O F   A  G I V E N   S T R I N G
//                                  RETURNS  A  VECTOR  OF  A  STRING

vector<string> possible_permutation(string s)
{
    sort(all(s));
    vstring v;
    do
    {
        v.pb(s);
    } while (next_permutation(all(s)));
    return v;
}

/* C O N V E R S I O N        T O              A N Y           N U M B E R          S Y S T E M     ________
        A N Y             N U M B E R       S Y S T E M            T O              D E C I M A L    _______*/

ll any_to_decimal(ll base, string s)
{
    reverse(all(s));
    ll ans = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int digit = s[i] - '0';
        ans += (digit * pow(base, i));
    }
    return ans;
}

//  P O W E R   O F   T W O   O R   N O T   ??
bool power_of_two(ll n)
{
    if (n == 0)
        return false;
    return !(n & (n - 1));
}

//   P R I M E    O R    N O T              ??

bool isPrime(int n)
{
    if (n < 2)
        return 0;
    for (int i = 2; i * i < n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}
long long numberOfDivisors(long long num)
{
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++)
    {
        if (num % i == 0)
        {
            int e = 0;
            do
            {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1)
    {
        total *= 2;
    }
    return total;
}

//   D I G I T A L        R O O T S          !!

string digital_roots(string s)
{
    while (s.size() > 1)
    {
        int ans = 0;
        for (auto x : s)
        {
            ans += (x - '0');
        }
        s = to_string(ans);
    }
    return s;
}
// Prototype for cheems function
void cheems();
ll calc_trailing_zero(ll n)
{
    ll ans = 0;
    ll mul = 5;
    while (n >= mul)
    {
        ans += (n / mul);
        mul *= 5;
    }
    return ans;
}
// Bubble sort
/*
time complexity: O(N^2) [Quadratic]
space complexity: O(N) [Linear]
Total pass/steps: N-1
operation: (n*(n-1))/2;
the summation from 1-n is :n*(n+1)/2 and this is given by gauss's law.

*/
ll find_gcm(ll a, ll b, ll c, ll X)
{
    ll ab_lcm = lcm(a, b);
    ll abc_lcm = lcm(ab_lcm, c);
    if (abc_lcm < X)
    {
        return abc_lcm;
    }
    else
    {
        return -1;
    }
}
void bubble_sort(int v[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        cout << "\nSteps no " << i + 1 << ":" << endl;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (v[j] > v[j + 1])
            {
                swap(v[j], v[j + 1]);
            }
            for (int k = 0; k < n; k++)
            {
                cout << v[k] << ' ';
            }
            cout << endl;
        }
    }
}
// Binary search
/*
Pre_requisite: Sorting the array.
Time complexity : O(logN)
Space complexity: O(N)
*/

//   M A I N   F U N C T I O N              !!

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    for (int i = 1; i <= _; i++)
    {
        cheems();
    }
}

//    V O I D     C H E E M S              !!

void cheems()
{
    long long a, b;
    cin >> a >> b;
    long long cnt = 0;
    while (a > 0 and b > 0)
    {
        cnt += max(a, b) / min(a, b);
        if (a > b)
            a %= b;
        else
            b %= a;
    }
    cout << cnt << endl;
}