#include<bits/stdc++.h>

using namespace std;
long long x[500005],z[500005];
long long gcd(long long x, long long y) {
	long long max_number = -9999;
	for (int i = 1; i <= min(x,y); i++) 
		if (x % i == 0 && y % i == 0 && i > max_number) 
			max_number = i;
	return max_number;
}
int main() {
	long long n;
	cin >> n;
	for (long long i = 1; i <= n; i++) 
		cin >> x[i] >> z[i];
	for (long long i = 1; i <= n; i++) {
		long long maxn = -9999;
		for (long long y = 1; y <= max(x[i],z[i]); y++) 
			if (z[i] == x[i] * y * gcd(x[i],y) && y > maxn) 
				maxn = y;
		if (maxn != -9999)
			cout << maxn << endl;
		else 
			cout << -1 << endl;
	}
	return 0;
}