#include <bits/stdc++.h>
using namespace std;
long long n,x,z,y;
long long gcd(long long a,long long b){
	return b?gcd(b,a%b):a;
}
int main(){
	cin>>n;
	while(n--){
		cin>>x>>z;
		if(z%x!=0){
			cout<<-1<<endl;
			continue;
		}
		if(sqrt(gcd(z/x,pow(x,2)))*sqrt(gcd(z/x,pow(x,2)))!=gcd(z/x,pow(x,2))){
			cout<<-1<<endl;
			continue;
		}
		else{
			long long res1=z/x;
			long long res2=sqrt(gcd(z/x,pow(x,2)));
			y=res1/res2;
			cout<<y<<endl;
		}
	}
	return 0;
}

60pts记录