#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);
    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=c-a; i>=0; i--) {
                for (int j=c-b; j>=0; j--) {
                    dp[i+a][j+b]=max(dp[i+a][j+b], dp[i][j]+1);
                }
            }
        }
    }
    int t;
    cin >> t;
    for (int i=1; i<=t; i++) {
        int x, y;
        cin >> x >> y;
        cout << dp[x][y] << "\n";
    }
    return 0;
}