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

int main() {
	vector<vector<int> > dp(501, vector<int>(501, 0));
	for (int x=1; x<32; x++) {
		for (int y=1; y<32; y++) {
			if (__gcd(x, y)==1) {
				for (int i=500; i>=x; i--) {
					for (int j=500; j>=y; j--) {
						dp[i][j]=max(dp[i][j], dp[i-x][j-y]+1);
					}
				}
			}
			
		}
	}

	int t;
	cin >> t;
	while (t--) {
		int x, y;
		cin >> x >> y;
		cout << dp[x][y] << "\n";
	}
}