#include <iostream>
#include <vector>

using namespace std;

size_t i, j, a, b, t;

int gcd(int x, int y)
{
	while (x != 0 && y != 0)
	{
		if (x <= y) y %= x;
		else x %= y;
	}

	return x + y;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	vector<vector<int>> dp(501, vector<int>(501, 0));

	for (i = 1; i < 32; ++i)
	{
		for (j = 1; j < 32; ++j)
		{
			if (gcd(i, j) == 1)
			{
				for (a = 500; a >= i; --a)
				{
					for (b = 500; b >= j; --b)
					{
						dp[a][b] = max(dp[a][b], dp[a - i][b - j] + 1);
					}
				}
			}
		}
	}

	cin >> t;
	for (i = 1; i <= t; ++i)
	{
		cin >> a >> b;
		cout << dp[a][b] << "\n";
	}
	return 0;
}
/*
3
4 4
2 3
2 2
*/