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

int main() {
	vector<vector<int> > relprim(500);
	relprim[1].push_back(1);
	for (int i=1; i<35; i++)
	{
		for (int j=1; j<min(i, 12); j++)
		{
			if (__gcd(i, j)==1)
			{
				relprim[i].push_back(j);
				relprim[j].push_back(i);
			}
		}
	}
	vector<vector<int> > dp(501, vector<int>(501));
	for(int i=1; i<35; i++) {
    for(int j: relprim[i]) {
      for(int a=500-i; a>=0; a--) {
        for(int b=500-j; b>=0; b--) {
          dp[a+i][b+j] = max(dp[a+i][b+j], dp[a][b]+1);
        }
      }
    }
  }
	int t, a, b;
	cin>>t;
	for (int i=0; i<t; i++)
	{
		cin>>a>>b;
		cout<<dp[a][b]<<"\n";
	}
}