#include<bits/stdc++.h>
using namespace std;
const int MAXN=505, SQRT=25;
int dp[SQRT][MAXN][MAXN];
vector<int> rel[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	
	for(int i=1;i<MAXN;++i) {
		for(int j=1;j<MAXN;++j) {
			if(gcd(i,j)==1) {
				rel[i].push_back(j);
			}
		}
	}
	
    for(int nxt=1;nxt<SQRT;++nxt) {
        for(int i=0;i<MAXN;++i) {
            for(int j=0;j<MAXN;++j) {
                if(i==0 || j==0) {
                    dp[nxt][i][j]=0;
                    continue ;
                }
                
                int mX=i, mY=j, cnt=0;
                int ans=dp[nxt-1][mX][mY];
                for(int yy:rel[nxt]) {
                    mX-=nxt;
                    mY-=yy;
                    cnt++;
		
                    if(mX<0 || mY<0) break ;
		
                    ans=max(ans, dp[nxt-1][mX][mY]+cnt);
                }
                
                dp[nxt][i][j]=ans;
            }
        }
    }
    
	int T;
	cin>>T;
	while(T--) {
		int x,y;
		cin>>x>>y;
		if(x>y) swap(x,y);
		cout<<dp[24][x][y]<<"\n";
	}
    return 0;
}