RT。

#include <bits/stdc++.h>
using namespace std;
int t, flag;
long long x, y, z, s, minn=1e18;
long long gcd(long long x, long long y){
	if (y == 0) return x;
	return gcd(y, x%y);
}
int main(){
	//freopen ("math.in", "r", stdin);
	//freopen ("math.out", "w", stdout);
	scanf ("%d", &t);
	while (t --){
		flag = 0;
		scanf ("%lld%lld", &x, &z);
		if (z < x || z % x){
			puts ("-1");
			continue;
		}
		z /= x, s = gcd(x, z);
		minn = 1e18;
		for (long long i=1; i<=sqrt(s); i++){
			if (s % i == 0){
				long long p1 = z / i, p2 = z / (s / i);
				//printf ("%lld %lld\n", p1, p2);
				if (gcd(p2, x) == s/i){
					printf ("%lld\n", p2);
					flag = 1;
					break;
				}
				if (gcd(p1, x) == i){
					minn = min(minn, p1);
				}
			}
		}
		if (flag == 0) printf ("%lld\n", minn == 1e18 ? -1 : minn);
	}
	return 0;
}