#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<vector<int>> dp(501, vector<int>(501, 0));

    for(int a = 1; a < 32; a++){
        for(int b = 1; b < 32; b++){
            if(a > 10 && b > 10 || __gcd(a, b) != 1) continue;

            for(int i = 500 - a; i >= 0; i--){
                for(int j = 500 - b; j >= 0; j--){
                    dp[i + a][j + b] = max(dp[i + a][j + b], dp[i][j] + 1);
                }
            }
        }
    }

    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        cout << dp[a][b] << "\n";
    }
}