#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,x,z;
ll gcd(ll a,ll b)
{
	if(a == 0) return b;
	if(b == 0) return a;
	if(!(a & 1) && !(b & 1))
		return gcd(a >> 1, b >> 1) << 1;
	else if(!(b & 1))
		return gcd(a, b >> 1);
	else if(!(a & 1))
		return gcd(a >> 1, b);
	else
		return gcd(abs(a - b), min(a, b));
}
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		bool flag=false;
		scanf("%lld %lld",&x,&z);
		if(z%x!=0)
		{
			printf("-1\n");
		}
		ll m=z/x;
		for(ll i=1;i<=m;i++)
		{
			if(x*i*gcd(x,i)==z)
			{
				printf("%lld\n",i);
				flag=true;
				break;
			}
		}
		if(flag==false)
		{
			printf("-1\n");
		}
	}
	return 0;
}