You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (*a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>). How many operations will be performed for each of them?
The first line contains the number of pairs *n* (1  ≤  *n*  ≤  1000). Then follow *n* lines, each line contains a pair of positive integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1  ≤  *a*<sub class="lower-index">*i*</sub>,  *b*<sub class="lower-index">*i*</sub>  ≤  10<sup class="upper-index">9</sup>).
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int long long
#define str string
#define endl "\n"
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define mem(arr, value) memset(arr, value, sizeof(arr))

const string space = " ";
const int MOD = 0;

int Mul(int a, int b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

int Sub(int a, int b)
{
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

int binary_expon(int base, int exp)
{ // O(log(exp))
    int ans = 1;
    if (exp == 0)
        return 1;
    if (exp % 2)
        ans = base;
    int temp = binary_expon(base, exp / 2);
    ans = Mul(ans, Mul(temp, temp)) % MOD;
    return ans;
}

int ModInv(int x)
{
    return binary_expon(x, MOD - 2);
}

int Div(int a, int b)
{
    return Mul(a, ModInv(b));
}

int Add(int a, int b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}

template <typename T>
void vin(vector<T> &vec, int start = 0)
{
    int n = vec.size();
    for (int i = start; i < n; i++)
        cin >> vec[i];
}

template <typename T>
void vin(deque<T> &vec, int start = 0)
{
    int n = vec.size();
    for (int i = start; i < n; i++)
        cin >> vec[i];
}

template <typename T>
void vout(vector<T> &vec, int start = 0)
{
    copy(vec.begin() + start, vec.end(), ostream_iterator<T>(cout, " "));
    cout << endl;
}

template <typename T>
void vout(deque<T> &vec, int start = 0)
{
    copy(vec.begin() + start, vec.end(), ostream_iterator<T>(cout, " "));
    cout << endl;
}

template <typename T>
void gridIn(vector<vector<T>> &vec, int start1 = 0, int start2 = 0)
{
    int x = vec.size();
    int y = vec[0].size();
    for (int i = start1; i < x; i++)
    {
        for (int u = start2; u < y; u++)
            cin >> vec[i][u];
    }
}

template <typename T>
void gridOut(vector<vector<T>> &vec, str space = " ")
{
    for (auto i : vec)
    {
        for (auto u : i)
            cout << u << space;
        cout << "\n";
    }
}

// fast checker
bool isPrime(int &n)
{
    if (n == 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (ll i = 3; i <= sqrt(n); i += 2)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

void FileInputOutput()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}

void FastIO()
{
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif // ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    FileInputOutput();
#endif
}

const int maxn = 100000 + 5;
bool primes[maxn];

void sieve()
{
    memset(primes, true, sizeof primes);
    primes[0] = false;
    primes[1] = false;
    for (int i = 2; i < maxn; ++i)
    {
        if (primes[i])
        {
            for (int j = i + i; j < maxn; j += i)
            {
                primes[j] = false;
            }
        }
    }
}

//    set<pair<int, int>, Compare> q;
//     priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> q;
struct Compare
{

    bool operator()(pair<int, int> l, pair<int, int> r) const
    {
        if (l.first == r.first)
        {
            return l.second > r.second;
        }
        return l.first < r.first;
    }
};

// O(log(b))
int powr(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res *= a;
        a *= a;
        b /= 2;
    }
    return res;
}

int NCR(int n, int k)
{
    int res = 1;

    if (k > n - k)
        k = n - k;

    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }

    return res;
}

const bool TEST_CASES = 1;
const bool __sieve = 0;
void Solve()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
    {
        swap(a, b);
    }
    int cntr = 0;
    while (a > 0 and b > 0)
    {
        int tem = max((ll)1, b / a);
        b -= (tem * a);
        cntr += tem;
        if (a > b)
        {
            swap(a, b);
        }
    }
    cout << cntr << endl;
}

void Code()
{
    if (__sieve)
        sieve();
    int t = 1;
    if (TEST_CASES)
        cin >> t;

    while (t--)
    {
        Solve();
    }
}

int32_t main()
{
    FastIO();
    Code();
}
