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

#ifdef DEBUG
ifstream in_file("C:\\verseny\\minta\\be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> pii;

ll T, A, B;
set<ll> s;

vector<pii> a, b;

int main() {
    for (ll i = 1; i <= 500; i++) {
        for (ll j = i+1; j <= 500; j++) {
            if (__gcd(i, j) == 1) {
                a.emplace_back(j, i);
                b.emplace_back(i, j);
            }
        }
    }
    
    input >> T;
    for (ll t = 0; t < T; t++) {
        input >> A >> B;
        A--; B--;
        ll c = 1;
        ll aind = 0, bind = 0;
        while (true) {
            if (A >= B && a[aind].first <= A && a[aind].second <= B) {
                c++;
                A -= a[aind].first;
                B -= a[aind].second;
                aind++;
            } else if (B > A && b[bind].first <= A && b[bind].second <= B) {
                c++;
                A -= b[bind].first;
                B -= b[bind].second;
                bind++;
            } else {
                break;
            }
        }
        cout << c << "\n";
    }
    cout << endl;
}