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

#pragma GCC optimize("Ofast")

signed main() {
    vector<pair<int, int>> vp;
    for (int i = 1; i <= 500; i++) {
        for (int j = 1; j <= 500; j++) {
            if (__gcd(i, j)==1&&(i<=30||j<=30))vp.push_back({i, j});
        }
    }
    vector<vector<int>> dp(501, vector<int>(501));
    for (auto p : vp) {
        auto [a, b] = p;
        for (int i = 500; i >= a; i--) {
            for (int j = 500; j >= b; j--) {
                dp[i][j]=max(dp[i][j], dp[i-a][j-b]+1);
            }
        }
        //cerr << a << ' ' << b << '\n';
    }
    int tt;
    cin >> tt;
    while (tt--) {
        int a, b;
        cin >> a >> b;
        cout << dp[a][b] << '\n';
    }
}