#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
int gcd(int a,int b){return a%b==0?(b):(gcd(b,a%b));}
signed main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	int t;scanf("%lld",&t);
	while (t--){
		int x,z;scanf("%lld%lld",&x,&z);
		if (z%x!=0) puts("-1");
		else{
			int yy=z/x,gy=gcd(z/x,x);
			int y=yy/gy,tag=0;
			if (gcd(x,y)*x*y==z){printf("%lld\n",y);continue;}
		//	printf("%lld %lld %lld %lld %lld\n",x,y,gcd(x,y),x*y*gcd(x,y),gy);
			for (int i=2;i<=gy;i++){
				int t=0;
				while (gy%i==0){gy/=i;t++;}
				int tt=0,ys=y;
				while (ys%i==0){ys/=i;tt++;}
				if (tt<t){
					if (tt==0 && t==1){tag=1;puts("-1");break;}
					if ((t+tt)%2!=0) y*=pow(i,(t+tt+1)/2-tt);//{puts("-1");tag=1;break;}
					else y*=pow(i,(t+tt)/2-tt);
				}
			}
			if (tag) continue;
		//	printf("%lld %lld %lld %lld %lld\n",x,y,gcd(x,y),x*y*gcd(x,y),gy);
			if (gcd(x,y)*x*y!=z) puts("-1");
			else printf("%lld\n",y);
		}
	}
	return 0;
} 

大样例140ms，能过吗？