#include<bits/stdc++.h>
using namespace std;
long long read(){
    char c=getchar();
	long long x=0;
	bool f=0;
    for(;!isdigit(c);c=getchar())
		f^=!(c^45);
    for(;isdigit(c);c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
    if(f)
		x=-x;
	return x;
}
void write(long long x){
	if(x<0)
		putchar('-'),x-=x*2;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
long long T,x,z,y,p[5000005],pos,idx,pr[50],pos1;
set<long long>s;
bool np[5000005];
void euler(int n){
	for(int i=2;i<=n;i++){
		if(!np[i])
			p[++pos]=i;
		for(int j=1;j<=pos&&i*p[j]<=n;j++){
			np[i*p[j]]=true;
			if(i%p[j]==0)
				break;
		}
	}
}
struct node{
	long long ls,x,len;
};
void bfs(long long len,long long d){
	queue<node>q;
	q.push({0,pr[d],len-1});
	while(!q.empty()){
		auto cur=q.front();
		q.pop();
		if(cur.len==0){
			long long tmp=cur.x;
			s.insert(tmp);
		}else{
			long long sd=cur.ls+1;
			long long x=pr[sd];
			q.push({sd,cur.x*pr[sd],cur.len-1});
			for(int i=sd+1;i<=pos1-cur.len+2;i++){
				if(pr[i]!=x)
					q.push({i,cur.x*pr[i],cur.len-1}),x=pr[i];
			}
		}
	}
}
int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	euler(5000000);
	T=read();
	while(T--){
		memset(pr,0,sizeof(pr));
		x=read(),z=read(),pos1=0;
		y=z/x;
		if(z%x!=0){
			puts("-1");
			continue;
		}
		idx=1;
		while(y>1&&p[idx]*p[idx]<=y){
			while(y%p[idx]==0){
				pr[++pos1]=p[idx];
				y/=p[idx];
			}
			idx++;
		}
		if(y)
			pr[++pos1]=y;
		bool f=false;
		for(int len=1;len<=pos1;len++){
			if(f)
				break;
			for(int j=1;j<=pos1-len+1;j++)
				bfs(len,j);
			for(auto &&it:s)
				if(it*x*__gcd(it,x)==z){
					write(it),puts("");
					f=true;
					break;
				}
			while(!s.empty())
				s.erase(*s.begin());
		}
		if(!f)
			puts("-1");
	}
	return 0;
}