#include<bits/stdc++.h>
using namespace std;
long long t,x,z;
long long gcd(long long a,long long b){
	return b==0?a:gcd(b,a%b);
}
bool issqr(long long n){
    int a=(long long)(sqrt(n)+0.5);  
    return a*a==n;
}
int main(){
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout); 
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&x,&z);
		if((z%x)!=0){
			printf("-1\n");
			continue;
		}
		if(issqr(z)||issqr(x)){
			if(issqr(z)&&issqr(x)){
				printf("%d\n",sqrt(z/x));
				continue;
			}
			printf("-1\n");
			continue;
		}
		if(x==z){
			printf("1\n");
			continue;
		}
		printf("%lld\n",z/x/gcd(z/x,x));
	}
	return 0;
}