#include<bits/stdc++.h>
using namespace std;
#define int long long 
int rd(){int Q;scanf("%lld",&Q);return Q;}
int t=rd(),gy;
int gcd(int x,int y){
    return y?gcd(y,x%y):x;
}
priority_queue<int,vector<int>,greater<int> >q;//优先队列能自动排序 
main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	while(t--){
		int x=rd(),y,z=rd(),flag=0;
		if(z%x==0)gy=z/x;//gcd(x,y)*y
		else {cout<<-1<<endl;continue;}//如果除不尽就-1  
		for(int i=1;i*i<=gy;i++){
			if(gy%i==0)q.push(i);
			if(i*i!=gy)q.push(gy/i);
		}//加入因数 
		while(!q.empty()){
			y=q.top();q.pop();//取出对头 
			if(z==x*y*gcd(x,y)){//原式 
				cout<<y<<endl;//输出 
				flag=1;
				break;//退出循环 
			}
		}if(flag==0)cout<<-1<<endl;
		while(!q.empty())q.pop();//清空，重置 
	}
	return 0;
}