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

const int maxN = 500;
const int MOD = 1e9 + 7;

short dp[501][501];


int main() {
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

    vector<pair<int, int>> v;

    for(int i = 1; i <= 38; i++) {
        for(int j = 1; j <= 30; j++) {
            if(__gcd(i, j) == 1) v.push_back({i, j});
        }
    }

    for(int i = 1; i <= v.size(); i++) {
        for(int j = maxN; j > 0; j--) {
            for(int l = maxN; l > 0; l--) {
                if(v[i-1].first <= j && v[i-1].second <= l) {
                    dp[j][l] = max(dp[j][l], (short)(dp[j - v[i-1].first][l - v[i-1].second] + 1));
                }
            }
        }
    }

    int t;
    cin >> t;
    while(t--) {
        int x,y;
        cin >> x >> y;

        cout << dp[x][y] << "\n";
    }

    return 0;
}