大样例过了，求估分。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int tt;
ll x,z;
struct ele{int v,k;};
ll gcd(ll xx,ll yy)
{
	return (!yy ? xx : gcd(yy,xx%yy));
}
bool Isp(ll x)
{
	for(ll i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			return 0;
		}
	}
	return 1;
}
void solve()
{
	scanf("%lld%lld",&x,&z);
	if(x>z||z%x)
	{
		printf("-1\n");
		return ;
	}
	if(x==z)
	{
		printf("1\n");
		return ;
	}
	ll a=z/x;
	if(Isp(a))
	{
		if(gcd(x,a)!=1)
			printf("-1\n");
		else printf("%lld\n",a);
		return ;
	}
	ll up=gcd(x,a);
	vector<ll>co;
	for(ll i=up;i>=1;i--)
	{
		if(x%i==0&&a%i==0)
		{
			if(i==gcd(a/i,x))
			{
				printf("%lld\n",a/i);
				return ;
			}
		}
	} 
}
int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin>>tt;
	while(tt--)
		solve();
	return 0;
}