#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > relprim(500);
vector<vector<vector<int> > > dp(501, vector<vector<int> >(501, vector<int>(35)));

int dpf(int a, int b, int i)
{
	if (dp[a][b][i])
	{
		return dp[a][b][i];
	}
	else
	{
		int ak=0; 
		int bk=0;
		for (int x : relprim[i])
		{
			ak+=i; bk+=x;
			if (a-ak<0||b-bk<0)
			{
				break;
			}
			else
			{
				dp[a][b][i]=max(dp[a][b][i], dpf(a-ak, b-bk, i+1)+ak/i);
			}
		}
		return dp[a][b][i];
	}
}

int main() {
	relprim[1].push_back(1);
	for (int i=1; i<500; i++)
	{
		for (int j=1; j<i; j++)
		{
			if (__gcd(i, j)==1)
			{
				relprim[i].push_back(j);
				relprim[j].push_back(i);
			}
		}
	}
	int t, a, b;
	cin>>t;
	for (int i=0; i<t; i++)
	{
		cin>>a>>b;
		cout<<dpf(a, b, 1)<<"\n";
	}
}