#define ll long long
#define ull unsigned long long
#define inf 2000000000
#define ldb long double
#define db double
#define ft float
#define myset(a,b,c,d) for(int i=b;i<=c;i++)a[i]=d;
using namespace std;

ll gcd(ll x,ll y)
{
	if(!y)return x;
	return gcd(y,x%y);
}
int main()
{
// 	freopen("math.in","r",stdin);
// 	freopen("math.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		int x;ll z;
		scanf("%d%lld",&x,&z);
		if(z%x)
		{
			printf("-1\n");
			continue;
		}
		z/=x;
		int i;
		ll ans=-1;
		
		int kk=1;
		if(x%2)
		{
			kk++;
		}
		for(i=1;i*i<=x;i+=kk)if(x%i==0){
			int k=x/i;
			
			if(z%(k*k)==0)
			{
				if(gcd(x,z/(k*k))==1)
				{
					ans=z/k;
					break;
				}
			}
		}
		
		if(ans!=-1)
		{
			printf("%lld\n",ans);
			continue;
		}
		for(i=i-kk;i;i-=kk)if(x%i==0){
			if(z%(i*i)==0)
			{
				if(gcd(x,z/i)==i)
				{
					ans=z/i;
					break;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}```