#include <bits/stdc++.h>

using namespace std;
const int c=500;
int dp[c+1][c+1];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    /*
    eszrevetelek: (a, b) csak akkor szerepelhet, ha a es b relativ prim
    ha (a, b) szerepel, akkor minden olyan (c, d) par is, ahol (c<a es d<b), tehat (a, 1) is (a-1, 1), (a-2, 1) ... (1, 1) is
    1+2+...+32=528>500, tehat (a, b) csak akkor szerepelhet, ha a<32 es b<32
    hasonlo szamolassal kijon, hogy nem eri meg olyat felvenni, ahol a>10 es b>10
    dp-vel ki lehet szamolni elore minden, dp[i][j] az (i, j)-re a megoldas

    idokomplexitas: 500^2*db, ahol db beveheto fozetek szama kevesebb mint 500
    lehet meg optimailizalni, de ez is eleg
    */
    for (int a=1; a<32; a++) {
        for (int b=1; b<32; b++) {
            if (a>10 && b>10 || __gcd(a, b)>1) continue;
            // az (a, b) part lehet hogy erdemes bevenni
            for (int i=c-a; i>=0; i--) {
                for (int j=c-b; j>=0; j--) {
                    // fontos hogy visszafele menjenek a for ciklusok, igy nem lehet tobbszor bevenni
                    dp[i+a][j+b]=max(dp[i+a][j+b], dp[i][j]+1);
                }
            }
        }
    }

    // mar csak ki kell irni az eredmenyeket
    int t;
    cin >> t;
    for (int i=1; i<=t; i++) {
        int x, y;
        cin >> x >> y;
        cout << dp[x][y] << "\n";
    }
    return 0;
}