#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef double db;
#define re register
#define inf 1e9+10
#define lim 100010
#define mod 998244353
#define max(a,b) a>=b?a:b
#define min(a,b) a<=b?a:b
inline ull rd(){
    ull x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
ull gcd(ull x,ull y){
	if (y)return gcd(y, x%y);		
    else return x;
} 	
ull mysqrt(ull x)
{
	if (x <= 0)	return 0;
	ull res = x;
	while (res*res > x)res = (res + x / res) / 2;
	return res;
}
ull t,x,z,a,l;
int main(){
//	freopen("math.in","r",stdin);
//	freopen("math.out","w",stdout);
	t=rd();
	while(t--){
		x=rd();z=rd();
		if(z%x!=0){
			printf("-1\n");
			continue;			
		}
		z/=x;
		l=z/gcd(x,z)/gcd(z/gcd(x,z),x);
		l=z/mysqrt(z/l);
		if(l*gcd(x,l)==z) printf("%llu\n",l);
		else puts("-1\n");
	}
	return 0;
}