#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
int t;
ll z,y,x;
ll gcd(ll x,ll y){
    if(y==0){
		return x;
	}
    return gcd(y,x%y);
}
int main(){
//	freopen("math.out","r",stdin);
//	freopen("math.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld%lld",&x,&z);
		if(z%x!=0){
			printf("-1\n");
			continue;
		}else{
			ll m=z/x;
			ll s=m/gcd(m,x);
			if(s<gcd(m,x)){
				printf("-1\n");
				continue;
			}
			printf("%lld\n",s);
		}
	}
	return 0;
}