#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
	long long minn=min(x,y),maxx=max(x,y);
	if(maxx%minn==0) return minn;
	else return gcd(minn,maxx%minn);
}
long long t,x,z;
bool b;
int main(){
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>x>>z;
		if(z%x!=0){
			cout<<-1<<endl;
			continue;
		}
		z/=x;
		for(int j=1;j<=x;j++){
			if(x%j!=0||z%j!=0||z%(j*j)!=0) continue;
			long long p=z/j/j;
			if(gcd(x/j,p)==1){
				cout<<j*p<<endl;b=1;
				break;
			}
		}
		if(!b) cout<<-1<<endl;
		b=0;
	}
	return 0;
}