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

int main() {
	vector<vector<int> > relprim(500);
	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);
			}
		}
	}
	vector<vector<vector<int> > > dp(501, vector<vector<int> >(501, vector<int>(501)));
	//a, b, i
	int ak, bk;
	for (int a=1; a<=500; a++)
	{
		for (int b=1; b<=500; b++)
		{
			for (int i=sqrt(2*a); i>0; i--)
			{
				ak=0; 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], dp[a-ak][b-bk][i+1]+ak/i);
					}
				}
				/*
				a darab van összesen az elsőből
				b darab a másodikból
				dp[a][b][i] = hány darabot tudunk csinálni maximum, ha az elsőből mindig legalább i-t használunk
				*/
				
			}
		}
	}
	int t, a, b;
	cin>>t;
	for (int i=0; i<t; i++)
	{
		cin>>a>>b;
		cout<<dp[a][b][1]<<"\n";
	}
}