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

bool m[32][32];

bool lnko(int a, int b) {
	int mm = a%b;
	while(mm != 0) {
		a = b;
		b = mm;
		mm = a%b;
	}
	if(b == 1) return true;
	return false;
}

int kov(int a, int b) {
	b++;
	while(!m[a][b]) b++;
	return b;
}

int elo(int a, int b) {
	b--;
	while(!m[a][b]) b--;
	return b;
}

int main() {
	for(int i = 1; i <= 31; i++) {
		m[i][0] = 1;
		for(int j = 1; j <= 31; j++)
			m[i][j] = lnko(i, j);
	}

	int t;
	cin >> t;
	while(t--) {
		int a, b;
		cin >> a >> b;
		if(a > b) swap(a, b);

		vector<int> v(min(a+1, 32), 0);
		int o = 0, p = 1, lk = 0;
		while(lk != INT_MAX) {
			lk = INT_MAX;
			int x = -1000, y = 1000;
			for(int i = 1; i <= p; i++) {
				int j = kov(i, v[i]);
				if(a < b) {
					if(i <= j && i + j < lk && (a-i >= 0 && b-j >= 0)) {
						lk = i + j;
						x = i;
						y = j;
					}
				} else if(a > b) {
					if(i >= j && i + j < lk && (a-i >= 0 && b-j >= 0)) {
						lk = i + j;
						x = i;
						y = j;
					}
				} else {
					if(i + j < lk || (i + j == lk && abs(i-j) < abs(x-y)) && (a-i >= 0 && b-j >= 0)) {
						lk = i + j;
						x = i;
						y = j;
					}
				}
			}
			if(lk != INT_MAX) {
				v[x] = y;
				o++;
				a -= x;
				b -= y;
				if(x == p) p++;
			}
		}

		cout << o-1 << '\n';
	}

	return 0;
}