#include<bits/stdc++.h>
using namespace std;
int main()
{
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	long long t,x,z,xy,flag=0,Y;
	cin>>t;
	for(long long i=1;i<=t;i++)
	{
		cin>>x>>z;
		for(long long y=1;y<=z;y++)
		{
			for(long long j=1;j<=y;j++)
			{
				if(x%j==0&&y%j==0)
				{
					xy=j;
				}
			}
			if(z==x*y*xy)
			{
				Y=y;
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			int bbb=-1;
			printf("%d\n",bbb);
		}
		else
		{
			cout<<Y;
		}
		flag=0;
	}
	return 0;
}