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