？

#include<bits/stdc++.h>
using namespace std;
int abcd(long long int m,long long int n)
{
	int i=m;
	for(i=m;;i--)
	{
		if(m%i==0 && n%i==0)
		{
			break;
		}
	}
	return i;
}
int main()
{
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	long long int x,z;
	long long int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		cin>>x>>z;
		for(int j=x+1;;j++)
		{
			if(x==z)
			{
				cout<<"1"<<endl;
				break;
			}
			else{
				if(x!=z)
				{
					if((abcd(x,j)*x*j)==z) 
					{
						cout<<j<<endl;
						break; 
					}
					if(z<(abcd(x,j)*x*j))
					{
						cout<<"-1"<<endl;
						break;
					}			
				}
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}