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

int main(){
    int dp[501][501];
    for (int a=1; a<32; a++){
        for (int b=1; b<32; b++){
            if (a>10 and b>10 or __gcd(a, b)>1) continue;
            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);
                }
            }
        }
    }
    int t;
    cin >> t;
    for (int i=1; i<=t; i++) {
        int x, y;
        cin >> x >> y;
        cout << dp[x][y] << "\n";
    }
}