#include<bits/stdc++.h>
using namespace std;
inline long long gcd(long long x,long long y) {
	if (x==0) return y;
	return gcd(y%x,x);
}
long long x,y,z,t,l,r;
int T;
int main(){
// 	freopen("math.in","r",stdin);
// 	freopen("math.out","w",stdout);
	scanf("%d",&T);
	while (T--) {
		bool flag=0;
		scanf("%lld %lld",&x,&z);
		if (z%x!=0) {
			printf("-1\n");
			continue;
		}
		t=z/x;
		l=gcd(x,t);
//		gcd|z/x
//		printf("%lld\n",l);
		if (gcd(t/l,x)==l) {
			printf("%lld\n",t/l);
			continue;
		}
		for (long long i=l/2;i>=1;i--) {//ö¾Ùgcd 
			if (l%i==0) {
				if (gcd(t/i,x)!=i) continue;
				flag=1;
				printf("%lld\n",t/i);
				break;
			}
		}
		if (!flag) printf("-1\n");
	}
	return 0;
}
/*
3
5 30
4 8
11 11
*/