#include <iostream>
#include <algorithm>

using namespace std;

const int N = 500;
int x[N + 1][N + 1];

int gcd(int i, int j) {
	int r = i % j;

	while (r){
		i = j;
		j = r;
		r = i % j;
	}

	return j;
}

int main() {
	
	for (int i = 1; i <= 32; ++i)
		for (int j = 1; j <= 32; ++j)
			if (gcd(i, j) == 1) {
				for (int a = N; a >= i; --a)
					for (int b = N; b >= j; --b)
						x[a][b] = max(x[a][b], x[a - i][b - j] + 1);
			}


	int T;
	cin >> T;
	while (T--) {
		int A, B;
		cin >> A >> B;
		cout << x[A][B] << '\n';
	}
	return 0;
}