#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;


int lnko(int a, int b)
{
	while (a!=0 && b != 0)
	{
		if (a > b)
		{
			a %= b;
		}
		else
		{
			b %= a;
		}
	}
	return a + b;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	vector<vector<int>> vec(501, vector<int>(501, 0));
	
	for (size_t i = 1; i < 32; i++)
	{
		for (size_t j = 1; j < 32; j++)
		{
			if (lnko(i, j) == 1)
			{
				for (size_t x = 500; x > i-1; x--)
				{
					for (size_t y = 500; y > j-1; y--)
					{
						vec[x][y] = max(vec[x][y], vec[x - i][y - j] + 1);
					}
				}
			}
		}
	}
	for (size_t i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << vec[a][b] << endl;
	}
	return 0;
}
/*
3
4 4
2 3
2 2
*/