#include<algorithm>
#include<iostream>
#define int long long
#define filein(x) freopen(x,"r",stdin)
#define fileout(x) freopen(x,"w",stdout)
#define ifile(x) freopen(x,"r",stdin)
#define ofile(x) freopen(x,"w",stdout)
#define iofile(x,y) freopen(x,"r",stdin),freopen(y,"w",stdout)
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	iofile("math.in","math.out");
	int t;
	cin>>t;
	while(t--)
	{
		long long x,z,w;
		cin>>x;
		cin>>z;
		if(z%x!=0)
		{
			cout<<-1<<endl;
			continue;
		}
		w=z/x;
		bool f=0;
		for(long long d=1;d*2ll<=x;++d)
		{
			if(x%d==0)
			{
				if(w%d!=0)
				{
					continue;
				}
				long long y=w/d;
				if(__gcd(x,y)==d)
				{
					cout<<y<<endl;
					f=1;
					break;
				}
			}
		}
		if(!f)
		{
			if(w%x==0)
			{
				long long y=w/x;
				if(__gcd(x,y)==x)
				{
					cout<<y<<endl;
					f=1;
				}
			}
		}
		if(!f)
		{
			cout<<-1<<endl;
		}
	}
	return 0;
}

官方大样例全过，求Hack