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

long long sir(long long A, long long B) {
    long long op = 0;

    while (A != 0 && B != 0) {
        if (A > B) {
            A = abs(A - B);
        } else {
            B = abs(B - A);
        }
        op++;
    }

    return op;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        long long A, B;
        cin >> A >> B;

        long long ans = sir(A, B);
        cout << ans << endl;
    }

    return 0;
}