// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
signed main() {
    vector<array<int,2>> aranyok;
    for(int i = 1;i<=67;i++){
        for(int j = i;j<=67;j++){
            if(__gcd(i,j)==1){
                aranyok.push_back({i,j});
                if(i!=j)aranyok.push_back({j,i});
            }
        }
    }
    vector<vector<int>> dp(501,vector<int>(501));
    for(auto [a,b]:aranyok){
        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);
            }
        }
    }
    /*for(int i = 0;i<10;i++){
        for(int j = 0;j<10;j++){
            cout<<dp[i][j]<<' ';
        }cout<<endl;
    }*/
    int t;cin>>t;
    while(t--){
        int a,b;cin>>a>>b;
        cout<<dp[a][b]<<endl;
    }
}