#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define N 500005

ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}

int t;

int main(){
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	cin>>t;
	while(t--){
		ll a,b;
		cin>>a>>b;
		if(b<a||b%a!=0){
			printf("-1\n");
			continue;
		}
		ll x=gcd(a*a,b);
		ll ans=b/x;
		ll now=ans;
		int flag=0;
		while(ans<=b){
			if(gcd(ans,a)==b/a/ans){
				printf("%lld\n",ans);
				flag=1; 
				break;
			}else{
				ans=ans+now;
			}
		}
		if(flag==0)printf("-1\n");
	}
	return 0;
}