#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	
	bool grid[33][33] = {0};
	int dp[501][501] = {0};
	for(int i = 1; i <= 32; i++) {
		for(int j = 1; j <= 32; j++) {
			if (gcd(i, j) == 1) {
				cerr << i << ' ' << j << endl;
				for(int a = 500; a > 0; a--) {
					for(int b = 500; b > 0; b--) {
						if (a-i >= 0 && b-j >= 0) dp[a][b] = max(dp[a][b], dp[a-i][b-j]+1);
					}
				}
			}
		}
	}

	int n;
	cin >> n;
	int x, y;

	for(int i = 0; i < n; i++) {
		cin >> x >> y;
		cout << dp[x][y] << '\n';
	}
	
	
	return 0;
	
}