#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair

int main(){
  int t, a, b;
  cin>>t;
  vector<vector<int> > dp(501, vector<int>(501, INT_MIN));
  vector<pair<int, int> > c;
  c.pb(mp(1, 1));
  for (int i=2; i<2*sqrt(500); i++)
  {
    for (int j=1; j<=i; j++)
    {
      if (__gcd(i, j) == 1)
      {
        c.pb(mp(i, j));
        c.pb(mp(j, i));
      }
    }
  }
  dp[0][0]=0;
  for (auto x : c)
  {
    for (int a=500; a>=0; a--)
    {
      for (int b=500; b>=0; b--)
      {
        if (a>=x.first&&b>=x.second)
        {
          dp[a][b] = max(dp[a][b], dp[a-x.first][b-x.second]+1);
        }
      }
    }
  }
  for (int a=1; a<501; a++)
  {
    for (int b=1; b<501; b++)
    {
      dp[a][b] = max(dp[a][b], max(dp[a][b-1], dp[a-1][b]));
    }
  }
  for (int i=0; i<t; i++)
  {
    cin>>a>>b;
    cout<<dp[a][b]<<"\n";
  }
  return 0;
}